diff options
| author | Joshua Oreman | 2009-07-21 20:16:38 +0200 |
|---|---|---|
| committer | Michael Brown | 2009-08-01 20:00:32 +0200 |
| commit | ce64398f87230d14a62b2ff153a67b851a125d2e (patch) | |
| tree | 8acc9c2ed28a23100b98626a25a67b09e2dbd2c0 /src/net/80211 | |
| parent | [hermon] Add support for RC queue pairs (diff) | |
| download | ipxe-ce64398f87230d14a62b2ff153a67b851a125d2e.tar.gz ipxe-ce64398f87230d14a62b2ff153a67b851a125d2e.tar.xz ipxe-ce64398f87230d14a62b2ff153a67b851a125d2e.zip | |
[802.11] Add support for 802.11 devices with software MAC layer
This is required for all modern 802.11 devices, and allows drivers
to be written for them with minimally more effort than is required
for a wired NIC.
Signed-off-by: Michael Brown <mcb30@etherboot.org>
Modified-by: Michael Brown <mcb30@etherboot.org>
Diffstat (limited to 'src/net/80211')
| -rw-r--r-- | src/net/80211/net80211.c | 2595 | ||||
| -rw-r--r-- | src/net/80211/rc80211.c | 371 |
2 files changed, 2966 insertions, 0 deletions
diff --git a/src/net/80211/net80211.c b/src/net/80211/net80211.c new file mode 100644 index 00000000..7d10aaa2 --- /dev/null +++ b/src/net/80211/net80211.c @@ -0,0 +1,2595 @@ +/* + * The gPXE 802.11 MAC layer. + * + * Copyright (c) 2009 Joshua Oreman <oremanj@rwcr.net>. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or any later version. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + */ + +FILE_LICENCE ( GPL2_OR_LATER ); + +#include <string.h> +#include <byteswap.h> +#include <stdlib.h> +#include <gpxe/settings.h> +#include <gpxe/if_arp.h> +#include <gpxe/ethernet.h> +#include <gpxe/ieee80211.h> +#include <gpxe/netdevice.h> +#include <gpxe/net80211.h> +#include <gpxe/timer.h> +#include <gpxe/nap.h> +#include <unistd.h> +#include <errno.h> + +/** @file + * + * 802.11 device management + */ + +/* Disambiguate the EINVAL's a bit */ +#define EINVAL_PKT_TOO_SHORT ( EINVAL | EUNIQ_01 ) +#define EINVAL_PKT_VERSION ( EINVAL | EUNIQ_02 ) +#define EINVAL_PKT_NOT_DATA ( EINVAL | EUNIQ_03 ) +#define EINVAL_PKT_NOT_FROMDS ( EINVAL | EUNIQ_04 ) +#define EINVAL_PKT_LLC_HEADER ( EINVAL | EUNIQ_05 ) +#define EINVAL_CRYPTO_REQUEST ( EINVAL | EUNIQ_06 ) +#define EINVAL_ACTIVE_SCAN ( EINVAL | EUNIQ_07 ) + +/* + * 802.11 error codes: The AP can give us a status code explaining why + * authentication failed, or a reason code explaining why we were + * deauthenticated/disassociated. These codes range from 0-63 (the + * field is 16 bits wide, but only up to 45 or so are defined yet; we + * allow up to 63 for extensibility). This is encoded into an error + * code as such: + * + * status & 0x1f goes here --vv-- + * Status code 0-31: ECONNREFUSED | EUNIQ_(status & 0x1f) (0e1a6038) + * Status code 32-63: EHOSTUNREACH | EUNIQ_(status & 0x1f) (171a6011) + * Reason code 0-31: ECONNRESET | EUNIQ_(reason & 0x1f) (0f1a6039) + * Reason code 32-63: ENETRESET | EUNIQ_(reason & 0x1f) (271a6001) + * + * The POSIX error codes more or less convey the appropriate message + * (status codes occur when we can't associate at all, reason codes + * when we lose association unexpectedly) and let us extract the + * complete 802.11 error code from the rc value. + */ + +/** Make return status code from 802.11 status code */ +#define E80211_STATUS( stat ) ( ((stat & 0x20)? EHOSTUNREACH : ECONNREFUSED) \ + | ((stat & 0x1f) << 8) ) + +/** Make return status code from 802.11 reason code */ +#define E80211_REASON( reas ) ( ((reas & 0x20)? ENETRESET : ECONNRESET) \ + | ((reas & 0x1f) << 8) ) + + +/** List of 802.11 devices */ +static struct list_head net80211_devices = LIST_HEAD_INIT ( net80211_devices ); + +/** Set of device operations that does nothing */ +static struct net80211_device_operations net80211_null_ops; + +/** Information associated with a received management packet + * + * This is used to keep beacon signal strengths in a parallel queue to + * the beacons themselves. + */ +struct net80211_rx_info { + int signal; + struct list_head list; +}; + +/** Context for a probe operation */ +struct net80211_probe_ctx { + /** 802.11 device to probe on */ + struct net80211_device *dev; + + /** Value of keep_mgmt before probe was started */ + int old_keep_mgmt; + + /** If scanning actively, pointer to probe packet to send */ + struct io_buffer *probe; + + /** If non-"", the ESSID to limit ourselves to */ + const char *essid; + + /** Time probe was started */ + u32 ticks_start; + + /** Time last useful beacon was received */ + u32 ticks_beacon; + + /** Time channel was last changed */ + u32 ticks_channel; + + /** Time to stay on each channel */ + u32 hop_time; + + /** Channels to hop by when changing channel */ + int hop_step; + + /** List of best beacons for each network found so far */ + struct list_head *beacons; +}; + +/** Context for the association task */ +struct net80211_assoc_ctx { + /** Next authentication method to try using */ + int method; + + /** Time (in ticks) of the last sent association-related packet */ + int last_packet; + + /** Number of times we have tried sending it */ + int times_tried; +}; + +/** + * @defgroup net80211_netdev Network device interface functions + * @{ + */ +static int net80211_netdev_open ( struct net_device *netdev ); +static void net80211_netdev_close ( struct net_device *netdev ); +static int net80211_netdev_transmit ( struct net_device *netdev, + struct io_buffer *iobuf ); +static void net80211_netdev_poll ( struct net_device *netdev ); +static void net80211_netdev_irq ( struct net_device *netdev, int enable ); +/** @} */ + +/** + * @defgroup net80211_linklayer 802.11 link-layer protocol functions + * @{ + */ +static u16 net80211_duration ( struct net80211_device *dev, int bytes ); +static int net80211_ll_push ( struct net_device *netdev, + struct io_buffer *iobuf, const void *ll_dest, + const void *ll_source, uint16_t net_proto ); +static int net80211_ll_pull ( struct net_device *netdev, + struct io_buffer *iobuf, const void **ll_dest, + const void **ll_source, uint16_t * net_proto ); +static int net80211_ll_mc_hash ( unsigned int af, const void *net_addr, + void *ll_addr ); +/** @} */ + +/** + * @defgroup net80211_help 802.11 helper functions + * @{ + */ +static void net80211_add_channels ( struct net80211_device *dev, int start, + int len, int txpower ); +static void net80211_set_rtscts_rate ( struct net80211_device *dev ); +static int net80211_process_capab ( struct net80211_device *dev, + u16 capab ); +static int net80211_process_ie ( struct net80211_device *dev, + union ieee80211_ie *ie, void *ie_end ); +static union ieee80211_ie * +net80211_marshal_request_info ( struct net80211_device *dev, + union ieee80211_ie *ie ); +/** @} */ + +/** + * @defgroup net80211_assoc_ll 802.11 association handling functions + * @{ + */ +static void net80211_step_associate ( struct process *proc ); +static void net80211_handle_auth ( struct net80211_device *dev, + struct io_buffer *iob ); +static void net80211_handle_assoc_reply ( struct net80211_device *dev, + struct io_buffer *iob ); +static int net80211_send_disassoc ( struct net80211_device *dev, int reason ); +static void net80211_handle_mgmt ( struct net80211_device *dev, + struct io_buffer *iob, int signal ); +/** @} */ + +/** + * @defgroup net80211_frag 802.11 fragment handling functions + * @{ + */ +static void net80211_free_frags ( struct net80211_device *dev, int fcid ); +static struct io_buffer *net80211_accum_frags ( struct net80211_device *dev, + int fcid, int nfrags, int size ); +static void net80211_rx_frag ( struct net80211_device *dev, + struct io_buffer *iob, int signal ); +/** @} */ + +/** + * @defgroup net80211_settings 802.11 settings handlers + * @{ + */ +static int net80211_check_ssid_update ( void ); + +/** 802.11 settings applicator + * + * When the SSID is changed, this will cause any open devices to + * re-associate. + */ +struct settings_applicator net80211_ssid_applicator __settings_applicator = { + .apply = net80211_check_ssid_update, +}; + +/** The network name to associate with + * + * If this is blank, we scan for all networks and use the one with the + * greatest signal strength. + */ +struct setting net80211_ssid_setting __setting = { + .name = "ssid", + .description = "802.11 SSID (network name)", + .type = &setting_type_string, +}; + +/** Whether to use active scanning + * + * In order to associate with a hidden SSID, it's necessary to use an + * active scan (send probe packets). If this setting is nonzero, an + * active scan on the 2.4GHz band will be used to associate. + */ +struct setting net80211_active_setting __setting = { + .name = "active-scan", + .description = "Use an active scan during 802.11 association", + .type = &setting_type_int8, +}; + +/** @} */ + + +/* ---------- net_device wrapper ---------- */ + +/** + * Open 802.11 device and start association + * + * @v netdev Wrapping network device + * @ret rc Return status code + * + * This sets up a default conservative set of channels for probing, + * and starts the auto-association task unless the @c + * NET80211_NO_ASSOC flag is set in the wrapped 802.11 device's @c + * state field. + */ +static int net80211_netdev_open ( struct net_device *netdev ) +{ + struct net80211_device *dev = netdev->priv; + int rc = 0; + + if ( dev->op == &net80211_null_ops ) + return -EFAULT; + + if ( dev->op->open ) + rc = dev->op->open ( dev ); + + if ( rc < 0 ) + return rc; + + if ( ! ( dev->state & NET80211_NO_ASSOC ) ) + net80211_autoassociate ( dev ); + + return 0; +} + +/** + * Close 802.11 device + * + * @v netdev Wrapping network device. + * + * If the association task is running, this will stop it. + */ +static void net80211_netdev_close ( struct net_device *netdev ) +{ + struct net80211_device *dev = netdev->priv; + + if ( dev->state & NET80211_WORKING ) + process_del ( &dev->proc_assoc ); + + /* Send disassociation frame to AP, to be polite */ + if ( dev->state & NET80211_ASSOCIATED ) + net80211_send_disassoc ( dev, IEEE80211_REASON_LEAVING ); + + netdev_link_down ( netdev ); + dev->state = 0; + + if ( dev->op->close ) + dev->op->close ( dev ); +} + +/** + * Transmit packet on 802.11 device + * + * @v netdev Wrapping network device + * @v iobuf I/O buffer + * @ret rc Return status code + * + * If encryption is enabled for the currently associated network, the + * packet will be encrypted prior to transmission. + */ +static int net80211_netdev_transmit ( struct net_device *netdev, + struct io_buffer *iobuf ) +{ + struct net80211_device *dev = netdev->priv; + int rc = -ENOSYS; + + if ( dev->crypto ) { + struct io_buffer *niob = dev->crypto->encrypt ( dev->crypto, + iobuf ); + if ( ! niob ) + return -ENOMEM; /* only reason encryption could fail */ + + free_iob ( iobuf ); + iobuf = niob; + } + + if ( dev->op->transmit ) + rc = dev->op->transmit ( dev, iobuf ); + + return rc; +} + +/** + * Poll 802.11 device for received packets and completed transmissions + * + * @v netdev Wrapping network device + */ +static void net80211_netdev_poll ( struct net_device *netdev ) +{ + struct net80211_device *dev = netdev->priv; + + if ( dev->op->poll ) + dev->op->poll ( dev ); +} + +/** + * Enable or disable interrupts for 802.11 device + * + * @v netdev Wrapping network device + * @v enable Whether to enable interrupts + */ +static void net80211_netdev_irq ( struct net_device *netdev, int enable ) +{ + struct net80211_device *dev = netdev->priv; + + if ( dev->op->irq ) + dev->op->irq ( dev, enable ); +} + +/** Network device operations for a wrapped 802.11 device */ +static struct net_device_operations net80211_netdev_ops = { + .open = net80211_netdev_open, + .close = net80211_netdev_close, + .transmit = net80211_netdev_transmit, + .poll = net80211_netdev_poll, + .irq = net80211_netdev_irq, +}; + + +/* ---------- 802.11 link-layer protocol ---------- */ + +/** 802.11 broadcast MAC address */ +static u8 net80211_ll_broadcast[] = { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff }; + +/** + * Determine whether a transmission rate uses ERP/OFDM + * + * @v rate Rate in 100 kbps units + * @ret is_erp TRUE if the rate is an ERP/OFDM rate + * + * 802.11b supports rates of 1.0, 2.0, 5.5, and 11.0 Mbps; any other + * rate than these on the 2.4GHz spectrum is an ERP (802.11g) rate. + */ +static inline int net80211_rate_is_erp ( u16 rate ) +{ + if ( rate == 10 || rate == 20 || rate == 55 || rate == 110 ) + return 0; + return 1; +} + + +/** + * Calculate one frame's contribution to 802.11 duration field + * + * @v dev 802.11 device + * @v bytes Amount of data to calculate duration for + * @ret dur Duration field in microseconds + * + * To avoid multiple stations attempting to transmit at once, 802.11 + * provides that every packet shall include a duration field + * specifying a length of time for which the wireless medium will be + * reserved after it is transmitted. The duration is measured in + * microseconds and is calculated with respect to the current + * physical-layer parameters of the 802.11 device. + * + * For an unfragmented data or management frame, or the last fragment + * of a fragmented frame, the duration captures only the 10 data bytes + * of one ACK; call once with bytes = 10. + * + * For a fragment of a data or management rame that will be followed + * by more fragments, the duration captures an ACK, the following + * fragment, and its ACK; add the results of three calls, two with + * bytes = 10 and one with bytes set to the next fragment's size. + * + * For an RTS control frame, the duration captures the responding CTS, + * the frame being sent, and its ACK; add the results of three calls, + * two with bytes = 10 and one with bytes set to the next frame's size + * (assuming unfragmented). + * + * For a CTS-to-self control frame, the duration captures the frame + * being protected and its ACK; add the results of two calls, one with + * bytes = 10 and one with bytes set to the next frame's size. + * + * No other frame types are currently supported by gPXE. + */ +static u16 net80211_duration ( struct net80211_device *dev, int bytes ) +{ + struct net80211_channel *chan = &dev->channels[dev->channel]; + u16 rate = dev->rates[dev->rate]; + u32 kbps = rate * 100; + + if ( chan->band == NET80211_BAND_5GHZ || net80211_rate_is_erp ( rate ) ) { + /* OFDM encoding (802.11a/g) */ + int bits_per_symbol = ( kbps * 4 ) / 1000; /* 4us/symbol */ + int bits = 22 + ( bytes << 3 ); /* 22-bit PLCP */ + int symbols = ( bits + bits_per_symbol - 1 ) / bits_per_symbol; + + return 16 + 20 + ( symbols * 4 ); /* 16us SIFS, 20us preamble */ + } else { + /* CCK encoding (802.11b) */ + int phy_time = 144 + 48; /* preamble + PLCP */ + int bits = bytes << 3; + int data_time = ( bits * 1000 + kbps - 1 ) / kbps; + + if ( dev->phy_flags & NET80211_PHY_USE_SHORT_PREAMBLE ) + phy_time >>= 1; + + return 10 + phy_time + data_time; /* 10us SIFS */ + } +} + +/** + * Add 802.11 link-layer header + * + * @v netdev Wrapping network device + * @v iobuf I/O buffer + * @v ll_dest Link-layer destination address + * @v ll_source Link-layer source address + * @v net_proto Network-layer protocol, in network byte order + * @ret rc Return status code + * + * This adds both the 802.11 frame header and the 802.2 LLC/SNAP + * header used on data packets. + * + * We also check here for state of the link that would make it invalid + * to send a data packet; every data packet must pass through here, + * and no non-data packet (e.g. management frame) should. + */ +static int net80211_ll_push ( struct net_device *netdev, + struct io_buffer *iobuf, const void *ll_dest, + const void *ll_source, uint16_t net_proto ) +{ + struct net80211_device *dev = netdev->priv; + struct ieee80211_frame *hdr = iob_push ( iobuf, + IEEE80211_LLC_HEADER_LEN + + IEEE80211_TYP_FRAME_HEADER_LEN ); + struct ieee80211_llc_snap_header *lhdr = + ( void * ) hdr + IEEE80211_TYP_FRAME_HEADER_LEN; + + /* We can't send data packets if we're not associated. */ + if ( ! netdev_link_ok ( netdev ) ) { + if ( dev->assoc_rc ) + return dev->assoc_rc; + return -ENETUNREACH; + } + + hdr->fc = IEEE80211_THIS_VERSION | IEEE80211_TYPE_DATA | + IEEE80211_STYPE_DATA | IEEE80211_FC_TODS; + + /* We don't send fragmented frames, so duration is the time + for an SIFS + 10-byte ACK. */ + hdr->duration = net80211_duration ( dev, 10 ); + + memcpy ( hdr->addr1, dev->bssid, ETH_ALEN ); + memcpy ( hdr->addr2, ll_source, ETH_ALEN ); + memcpy ( hdr->addr3, ll_dest, ETH_ALEN ); + + hdr->seq = IEEE80211_MAKESEQ ( ++dev->last_tx_seqnr, 0 ); + + lhdr->dsap = IEEE80211_LLC_DSAP; + lhdr->ssap = IEEE80211_LLC_SSAP; + lhdr->ctrl = IEEE80211_LLC_CTRL; + memset ( lhdr->oui, 0x00, 3 ); + lhdr->ethertype = net_proto; + + return 0; +} + +/** + * Remove 802.11 link-layer header + * + * @v netdev Wrapping network device + * @v iobuf I/O buffer + * @ret ll_dest Link-layer destination address + * @ret ll_source Link-layer source + * @ret net_proto Network-layer protocol, in network byte order + * @ret rc Return status code + * + * This expects and removes both the 802.11 frame header and the 802.2 + * LLC/SNAP header that are used on data packets. + */ +static int net80211_ll_pull ( struct net_device *netdev __unused, + struct io_buffer *iobuf, + const void **ll_dest, const void **ll_source, + uint16_t * net_proto ) +{ + struct ieee80211_frame *hdr = iobuf->data; + struct ieee80211_llc_snap_header *lhdr = + ( void * ) hdr + IEEE80211_TYP_FRAME_HEADER_LEN; + + /* Bunch of sanity checks */ + if ( iob_len ( iobuf ) < IEEE80211_TYP_FRAME_HEADER_LEN + + IEEE80211_LLC_HEADER_LEN ) { + DBGC ( netdev->priv, "802.11 %p packet too short (%zd bytes)\n", + netdev->priv, iob_len ( iobuf ) ); + return -EINVAL_PKT_TOO_SHORT; + } + + if ( ( hdr->fc & IEEE80211_FC_VERSION ) != IEEE80211_THIS_VERSION ) { + DBGC ( netdev->priv, "802.11 %p packet invalid version %04x\n", + netdev->priv, hdr->fc & IEEE80211_FC_VERSION ); + return -EINVAL_PKT_VERSION; + } + + if ( ( hdr->fc & IEEE80211_FC_TYPE ) != IEEE80211_TYPE_DATA || + ( hdr->fc & IEEE80211_FC_SUBTYPE ) != IEEE80211_STYPE_DATA ) { + DBGC ( netdev->priv, "802.11 %p packet not data/data (fc=%04x)\n", + netdev->priv, hdr->fc ); + return -EINVAL_PKT_NOT_DATA; + } + + if ( ( hdr->fc & ( IEEE80211_FC_TODS | IEEE80211_FC_FROMDS ) ) != + IEEE80211_FC_FROMDS ) { + DBGC ( netdev->priv, "802.11 %p packet not from DS (fc=%04x)\n", + netdev->priv, hdr->fc ); + return -EINVAL_PKT_NOT_FROMDS; + } + + if ( lhdr->dsap != IEEE80211_LLC_DSAP || lhdr->ssap != IEEE80211_LLC_SSAP || + lhdr->ctrl != IEEE80211_LLC_CTRL || lhdr->oui[0] || lhdr->oui[1] || + lhdr->oui[2] ) { + DBGC ( netdev->priv, "802.11 %p LLC header is not plain EtherType " + "encapsulator: %02x->%02x [%02x] %02x:%02x:%02x %04x\n", + netdev->priv, lhdr->dsap, lhdr->ssap, lhdr->ctrl, + lhdr->oui[0], lhdr->oui[1], lhdr->oui[2], lhdr->ethertype ); + return -EINVAL_PKT_LLC_HEADER; + } + + iob_pull ( iobuf, sizeof ( *hdr ) + sizeof ( *lhdr ) ); + + *ll_dest = hdr->addr1; + *ll_source = hdr->addr3; + *net_proto = lhdr->ethertype; + return 0; +} + +/** + * Hash 802.11 multicast address + * + * @v af Address family + * @v net_addr Network-layer address + * @ret ll_addr Filled link-layer address + * @ret rc Return status code + * + * Currently unimplemented. + */ +static int net80211_ll_mc_hash ( unsigned int af __unused, + const void *net_addr __unused, + void *ll_addr __unused ) +{ + return -ENOTSUP; +} + +/** 802.11 link-layer protocol */ +static struct ll_protocol net80211_ll_protocol __ll_protocol = { + .name = "802.11", + .push = net80211_ll_push, + .pull = net80211_ll_pull, + .ntoa = eth_ntoa, + .mc_hash = net80211_ll_mc_hash, + .ll_proto = htons ( ARPHRD_ETHER ), /* "encapsulated Ethernet" */ + .ll_addr_len = ETH_ALEN, + .ll_header_len = IEEE80211_TYP_FRAME_HEADER_LEN + + IEEE80211_LLC_HEADER_LEN, +}; + + +/* ---------- 802.11 network management API ---------- */ + +/** + * Get 802.11 device from wrapping network device + * + * @v netdev Wrapping network device + * @ret dev 802.11 device wrapped by network device, or NULL + * + * Returns NULL if the network device does not wrap an 802.11 device. + */ +struct net80211_device * net80211_get ( struct net_device *netdev ) +{ + struct net80211_device *dev; + + list_for_each_entry ( dev, &net80211_devices, list ) { + if ( netdev->priv == dev ) + return netdev->priv; + } + + return NULL; +} + +/** + * Set state of 802.11 device keeping management frames + * + * @v dev 802.11 device + * @v enable Whether to keep management frames + * @ret oldenab Whether management frames were enabled before this call + * + * If enable is TRUE, beacon, probe, and action frames will be kept + * and may be retrieved by calling net80211_mgmt_dequeue(). + */ +int net80211_keep_mgmt ( struct net80211_device *dev, int enable ) +{ + int oldenab = dev->keep_mgmt; + + dev->keep_mgmt = enable; + return oldenab; +} + +/** + * Get 802.11 management frame + * + * @v dev 802.11 device + * @ret signal Signal strength of returned management frame + * @ret iob I/O buffer, or NULL if no management frame is queued + * + * Frames will only be returned by this function if + * net80211_keep_mgmt() has been previously called with enable set to + * TRUE. + * + * The calling function takes ownership of the returned I/O buffer. + */ +struct io_buffer * net80211_mgmt_dequeue ( struct net80211_device *dev, + int *signal ) +{ + struct io_buffer *iobuf; + struct net80211_rx_info *rxi; + + list_for_each_entry ( rxi, &dev->mgmt_info_queue, list ) { + list_del ( &rxi->list ); + if ( signal ) + *signal = rxi->signal; + free ( rxi ); + + list_for_each_entry ( iobuf, &dev->mgmt_queue, list ) { + list_del ( &iobuf->list ); + return iobuf; + } + assert ( 0 ); + } + + return NULL; +} + +/** + * Transmit 802.11 management frame + * + * @v dev 802.11 device + * @v fc Frame Control flags for management frame + * @v dest Destination access point + * @v iob I/O buffer + * @ret rc Return status code + * + * The @a fc argument must contain at least an IEEE 802.11 management + * subtype number (e.g. IEEE80211_STYPE_PROBE_REQ). If it contains + * IEEE80211_FC_PROTECTED, the frame will be encrypted prior to + * transmission. + * + * It is required that @a iob have at least 24 bytes of headroom + * reserved before its data start. + */ +int net80211_tx_mgmt ( struct net80211_device *dev, u16 fc, u8 dest[6], + struct io_buffer *iob ) +{ + struct ieee80211_frame *hdr = iob_push ( iob, + IEEE80211_TYP_FRAME_HEADER_LEN ); + + hdr->fc = IEEE80211_THIS_VERSION | IEEE80211_TYPE_MGMT | + ( fc & ~IEEE80211_FC_PROTECTED ); + hdr->duration = net80211_duration ( dev, 10 ); + hdr->seq = IEEE80211_MAKESEQ ( ++dev->last_tx_seqnr, 0 ); + + memcpy ( hdr->addr1, dest, ETH_ALEN ); /* DA = RA */ + memcpy ( hdr->addr2, dev->netdev->ll_addr, ETH_ALEN ); /* SA = TA */ + memcpy ( hdr->addr3, dest, ETH_ALEN ); /* BSSID */ + + if ( fc & IEEE80211_FC_PROTECTED ) { + if ( ! dev->crypto ) + return -EINVAL_CRYPTO_REQUEST; + + struct io_buffer *eiob = dev->crypto->encrypt ( dev->crypto, + iob ); + free_iob ( iob ); + iob = eiob; + } + + return netdev_tx ( dev->netdev, iob ); +} + + +/* ---------- Driver API ---------- */ + +/** + * Allocate 802.11 device + * + * @v priv_size Size of driver-private allocation area + * @ret dev Newly allocated 802.11 device + * + * This function allocates a net_device with space in its private area + * for both the net80211_device it will wrap and the driver-private + * data space requested. It initializes the link-layer-specific parts + * of the net_device, and links the net80211_device to the net_device + * appropriately. + */ +struct net80211_device * net80211_alloc ( size_t priv_size ) +{ + struct net80211_device *dev; + struct net_device *netdev = + alloc_netdev ( sizeof ( *dev ) + priv_size ); + + if ( ! netdev ) + return NULL; + + netdev->ll_protocol = &net80211_ll_protocol; + netdev->ll_broadcast = net80211_ll_broadcast; + netdev->max_pkt_len = IEEE80211_MAX_DATA_LEN; + netdev_init ( netdev, &net80211_netdev_ops ); + + dev = netdev->priv; + dev->netdev = netdev; + dev->priv = ( u8 * ) dev + sizeof ( *dev ); + dev->op = &net80211_null_ops; + + dev->proc_assoc.step = net80211_step_associate; + INIT_LIST_HEAD ( &dev->mgmt_queue ); + INIT_LIST_HEAD ( &dev->mgmt_info_queue ); + + return dev; +} + +/** + * Register 802.11 device with network stack + * + * @v dev 802.11 device + * @v ops 802.11 device operations + * @v hw 802.11 hardware information + * + * This also registers the wrapping net_device with the higher network + * layers. + */ +int net80211_register ( struct net80211_device *dev, + struct net80211_device_operations *ops, + struct net80211_hw_info *hw ) +{ + dev->op = ops; + dev->hw = malloc ( sizeof ( *hw ) ); + if ( ! dev->hw ) + return -ENOMEM; + + memcpy ( dev->hw, hw, sizeof ( *hw ) ); + memcpy ( dev->netdev->ll_addr, hw->hwaddr, ETH_ALEN ); + + list_add_tail ( &dev->list, &net80211_devices ); + return register_netdev ( dev->netdev ); +} + +/** + * Unregister 802.11 device from network stack + * + * @v dev 802.11 device + * + * After this call, the device operations are cleared so that they + * will not be called. + */ +void net80211_unregister ( struct net80211_device *dev ) +{ + unregister_netdev ( dev->netdev ); + list_del ( &dev->list ); + dev->op = &net80211_null_ops; +} + +/** + * Free 802.11 device + * + * @v dev 802.11 device + * + * The device should be unregistered before this function is called. + */ +void net80211_free ( struct net80211_device *dev ) +{ + free ( dev->hw ); + rc80211_free ( dev->rctl ); + netdev_nullify ( dev->netdev ); + netdev_put ( dev->netdev ); +} + + +/* ---------- 802.11 network management workhorse code ---------- */ + +/** + * Set state of 802.11 device + * + * @v dev 802.11 device + * @v clear Bitmask of flags to clear + * @v set Bitmask of flags to set + * @v status Status or reason code for most recent operation + * + * If @a status represents a reason code, it should be OR'ed with + * NET80211_IS_REASON. + * + * Clearing authentication also clears association; clearing + * association also clears security handshaking state. Clearing + * association removes the link-up flag from the wrapping net_device, + * but setting it does not automatically set the flag; that is left to + * the judgment of higher-level code. + */ +static inline void net80211_set_state ( struct net80211_device *dev, + short clear, short set, + u16 status ) +{ + /* The conditions in this function are deliberately formulated + to be decidable at compile-time in most cases. Since clear + and set are generally passed as constants, the body of this + function can be reduced down to a few statements by the + compiler. */ + + const int statmsk = NET80211_STATUS_MASK | NET80211_IS_REASON; + + if ( clear & NET80211_PROBED ) + clear |= NET80211_AUTHENTICATED; + + if ( clear & NET80211_AUTHENTICATED ) + clear |= NET80211_ASSOCIATED; + + if ( clear & NET80211_ASSOCIATED ) + clear |= NET80211_CRYPTO_SYNCED; + + dev->state = ( dev->state & ~clear ) | set; + dev->state = ( dev->state & ~statmsk ) | ( status & statmsk ); + + if ( clear & NET80211_ASSOCIATED ) + netdev_link_down ( dev->netdev ); + + if ( ( clear | set ) & NET80211_ASSOCIATED ) + dev->op->config ( dev, NET80211_CFG_ASSOC ); + + if ( status != 0 ) { + if ( status & NET80211_IS_REASON ) + dev->assoc_rc = -E80211_REASON ( status ); + else + dev->assoc_rc = -E80211_STATUS ( status ); + netdev_link_err ( dev->netdev, dev->assoc_rc ); + } +} + +/** + * Add channels to 802.11 device + * + * @v dev 802.11 device + * @v start First channel number to add + * @v len Number of channels to add + * @v txpower TX power (dBm) to allow on added channels + * + * To replace the current list of channels instead of adding to it, + * set the nr_channels field of the 802.11 device to 0 before calling + * this function. + */ +static void net80211_add_channels ( struct net80211_device *dev, int start, + int len, int txpower ) +{ + int i, chan = start; + + for ( i = dev->nr_channels; len-- && i < NET80211_MAX_CHANNELS; i++ ) { + dev->channels[i].channel_nr = chan; + dev->channels[i].maxpower = txpower; + + if ( chan >= 1 && chan <= 14 ) { + dev->channels[i].band = NET80211_BAND_2GHZ; + if ( chan == 14 ) + dev->channels[i].center_freq = 2484; + else + dev->channels[i].center_freq = 2407 + 5 * chan; + chan++; + } else { + dev->channels[i].band = NET80211_BAND_5GHZ; + dev->channels[i].center_freq = 5000 + 5 * chan; + chan += 4; + } + } + + dev->nr_channels = i; +} + +/** + * Update 802.11 device state to reflect received capabilities field + * + * @v dev 802.11 device + * @v capab Capabilities field in beacon, probe, or association frame + * @ret rc Return status code + */ +static int net80211_process_capab ( struct net80211_device *dev, + u16 capab ) +{ + u16 old_phy = dev->phy_flags; + + if ( ( capab & ( IEEE80211_CAPAB_MANAGED | IEEE80211_CAPAB_ADHOC ) ) != + IEEE80211_CAPAB_MANAGED ) { + DBGC ( dev, "802.11 %p cannot handle IBSS network\n", dev ); + return -ENOSYS; + } + + if ( capab & IEEE80211_CAPAB_SPECTRUM_MGMT ) { + DBGC ( dev, "802.11 %p cannot handle spectrum managed " + "network\n", dev ); + return -ENOSYS; + } + + dev->phy_flags &= ~( NET80211_PHY_USE_SHORT_PREAMBLE | + NET80211_PHY_USE_SHORT_SLOT ); + + if ( capab & IEEE80211_CAPAB_SHORT_PMBL ) + dev->phy_flags |= NET80211_PHY_USE_SHORT_PREAMBLE; + + if ( capab & IEEE80211_CAPAB_SHORT_SLOT ) + dev->phy_flags |= NET80211_PHY_USE_SHORT_SLOT; + + if ( old_phy != dev->phy_flags ) + dev->op->config ( dev, NET80211_CFG_PHY_PARAMS ); + + return 0; +} + +/** + * Update 802.11 device state to reflect received information elements + * + * @v dev 802.11 device + * @v ie Pointer to first information element + * @v ie_end Pointer to tail of packet I/O buffer + * @ret rc Return status code + */ +static int net80211_process_ie ( struct net80211_device *dev, + union ieee80211_ie *ie, void *ie_end ) +{ + u16 old_rate = dev->rates[dev->rate]; + u16 old_phy = dev->phy_flags; + int have_rates = 0, i; + int ds_channel = 0; + int changed = 0; + + if ( ( void * ) ie >= ie_end ) + return 0; + + for ( ; ie; ie = ieee80211_next_ie ( ie, ie_end ) ) { + switch ( ie->id ) { + case IEEE80211_IE_SSID: + if ( ie->len <= 32 ) { + memcpy ( dev->essid, ie->ssid, ie->len ); + dev->essid[ie->len] = 0; + } + break; + + case IEEE80211_IE_RATES: + case IEEE80211_IE_EXT_RATES: + if ( ! have_rates ) { + dev->nr_rates = 0; + dev->basic_rates = 0; + have_rates = 1; + } + for ( i = 0; i < ie->len && + dev->nr_rates < NET80211_MAX_RATES; i++ ) { + u8 rid = ie->rates[i]; + u16 rate = ( rid & 0x7f ) * 5; + + if ( rid & 0x80 ) + dev->basic_rates |= + ( 1 << dev->nr_rates ); + + dev->rates[dev->nr_rates++] = rate; + } + + break; + + case IEEE80211_IE_DS_PARAM: + if ( dev->channel < dev->nr_channels && ds_channel == + dev->channels[dev->channel].channel_nr ) + break; + ds_channel = ie->ds_param.current_channel; + net80211_change_channel ( dev, ds_channel ); + break; + + case IEEE80211_IE_COUNTRY: + dev->nr_channels = 0; + + DBGC ( dev, "802.11 %p setting country regulations " + "for %c%c\n", dev, ie->country.name[0], + ie->country.name[1] ); + for ( i = 0; i < ( ie->len - 3 ) / 3; i++ ) { + union ieee80211_ie_country_triplet *t = + &ie->country.triplet[i]; + if ( t->first > 200 ) { + DBGC ( dev, "802.11 %p ignoring regulatory " + "extension information\n", dev ); + } else { + net80211_add_channels ( dev, + t->band.first_channel, + t->band.nr_channels, + t->band.max_txpower ); + } + } + break; + + case IEEE80211_IE_ERP_INFO: + dev->phy_flags &= ~( NET80211_PHY_USE_PROTECTION | + NET80211_PHY_USE_SHORT_PREAMBLE ); + if ( ie->erp_info & IEEE80211_ERP_USE_PROTECTION ) + dev->phy_flags |= NET80211_PHY_USE_PROTECTION; + if ( ! ( ie->erp_info & IEEE80211_ERP_BARKER_LONG ) ) + dev->phy_flags |= NET80211_PHY_USE_SHORT_PREAMBLE; + break; + + case IEEE80211_IE_RSN: + /* XXX need to implement WPA stuff */ + break; + } + } + + if ( have_rates ) { + /* Allow only those rates that are also supported by + the hardware. */ + int delta = 0, j; + + dev->rate = 0; + for ( i = 0; i < dev->nr_rates; i++ ) { + int ok = 0; + for ( j = 0; j < dev->hw->nr_supported_rates; j++ ) { + if ( dev->hw->supported_rates[j] == + dev->rates[i] ) { + ok = 1; + break; + } + } + + if ( ! ok ) + delta++; + else { + dev->rates[i - delta] = dev->rates[i]; + if ( old_rate == dev->rates[i] ) + dev->rate = i - delta; + } + } + + dev->nr_rates -= delta; + + /* Sort available rates - sorted subclumps tend to already + exist, so insertion sort works well. */ + for ( i = 1; i < dev->nr_rates; i++ ) { + u16 rate = dev->rates[i]; + + for ( j = i - 1; j >= 0 && dev->rates[j] >= rate; j-- ) + dev->rates[j + 1] = dev->rates[j]; + dev->rates[j + 1] = rate; + } + + net80211_set_rtscts_rate ( dev ); + + if ( dev->rates[dev->rate] != old_rate ) + changed |= NET80211_CFG_RATE; + } + + if ( dev->hw->flags & NET80211_HW_NO_SHORT_PREAMBLE ) + dev->phy_flags &= ~NET80211_PHY_USE_SHORT_PREAMBLE; + if ( dev->hw->flags & NET80211_HW_NO_SHORT_SLOT ) + dev->phy_flags &= ~NET80211_PHY_USE_SHORT_SLOT; + + if ( old_phy != dev->phy_flags ) + changed |= NET80211_CFG_PHY_PARAMS; + + if ( changed ) + dev->op->config ( dev, changed ); + + return 0; +} + +/** + * Create information elements for outgoing probe or association packet + * + * @v dev 802.11 device + * @v ie Pointer to start of information element area + * @ret next_ie Pointer to first byte after added information elements + */ +static union ieee80211_ie * +net80211_marshal_request_info ( struct net80211_device *dev, + union ieee80211_ie *ie ) +{ + int i; + + ie->id = IEEE80211_IE_SSID; + ie->len = strlen ( dev->essid ); + memcpy ( ie->ssid, dev->essid, ie->len ); + + ie = ieee80211_next_ie ( ie, NULL ); + + ie->id = IEEE80211_IE_RATES; + ie->len = dev->nr_rates; + for ( i = 0; i < ie->len; i++ ) { + ie->rates[i] = dev->rates[i] / 5; + if ( dev->basic_rates & ( 1 << i ) ) + ie->rates[i] |= 0x80; + } + + if ( ie->len > 8 ) { + /* 802.11 requires we use an Extended Basic Rates IE + for the rates beyond the eighth. */ + int rates = ie->len; + + memmove ( ( void * ) ie + 2 + 8 + 2, ( void * ) ie + 2 + 8, + rates - 8 ); + ie->len = 8; + + ie = ieee80211_next_ie ( ie, NULL ); + + ie->id = IEEE80211_IE_EXT_RATES; + ie->len = rates - 8; + } + + ie = ieee80211_next_ie ( ie, NULL ); + + return ie; +} + +/** Seconds to wait after finding a network, to possibly find better APs for it + * + * This is used when a specific SSID to scan for is specified. + */ +#define NET80211_PROBE_GATHER 1 + +/** Seconds to wait after finding a network, to possibly find other networks + * + * This is used when an empty SSID is specified, to scan for all + * networks. + */ +#define NET80211_PROBE_GATHER_ALL 2 + +/** Seconds to allow a probe to take if no network has been found */ +#define NET80211_PROBE_TIMEOUT 6 + +/** + * Begin probe of 802.11 networks + * + * @v dev 802.11 device + * @v essid SSID to probe for, or "" to accept any (may not be NULL) + * @v active Whether to use active scanning + * @ret ctx Probe context + * + * Active scanning may only be used on channels 1-11 in the 2.4GHz + * band, due to gPXE's lack of a complete regulatory database. If + * active scanning is used, probe packets will be sent on each + * channel; this can allow association with hidden-SSID networks if + * the SSID is properly specified. + * + * A @c NULL return indicates an out-of-memory condition. + * + * The returned context must be periodically passed to + * net80211_probe_step() until that function returns zero. + */ +struct net80211_probe_ctx * net80211_probe_start ( struct net80211_device *dev, + const char *essid, + int active ) +{ + struct net80211_probe_ctx *ctx = zalloc ( sizeof ( *ctx ) ); + + if ( ! ctx ) + return NULL; + + assert ( dev->netdev->state & NETDEV_OPEN ); + + ctx->dev = dev; + ctx->old_keep_mgmt = net80211_keep_mgmt ( dev, 1 ); + ctx->essid = essid; + if ( dev->essid != ctx->essid ) + strcpy ( dev->essid, ctx->essid ); + + if ( active ) { + struct ieee80211_probe_req *probe_req; + union ieee80211_ie *ie; + + ctx->probe = alloc_iob ( 128 ); + iob_reserve ( ctx->probe, IEEE80211_TYP_FRAME_HEADER_LEN ); + probe_req = ctx->probe->data; + + ie = net80211_marshal_request_info ( dev, + probe_req->info_element ); + ie->id = IEEE80211_IE_REQUEST; + ie->len = 3; + ie->request[0] = IEEE80211_IE_COUNTRY; + ie->request[1] = IEEE80211_IE_ERP_INFO; + ie->request[2] = IEEE80211_IE_RSN; + + ie = ieee80211_next_ie ( ie, NULL ); + + iob_put ( ctx->probe, ( void * ) ie - ctx->probe->data ); + } + + ctx->ticks_start = currticks(); + ctx->ticks_beacon = 0; + ctx->ticks_channel = currticks(); + ctx->hop_time = ticks_per_sec() / ( active ? 2 : 6 ); + + /* + * Channels on 2.4GHz overlap, and the most commonly used + * are 1, 6, and 11. We'll get a result faster if we check + * every 5 channels, but in order to hit all of them the + * number of channels must be relatively prime to 5. If it's + * not, tweak the hop. + */ + ctx->hop_step = 5; + while ( dev->nr_channels % ctx->hop_step == 0 && ctx->hop_step > 1 ) + ctx->hop_step--; + + ctx->beacons = malloc ( sizeof ( *ctx->beacons ) ); + INIT_LIST_HEAD ( ctx->beacons ); + + dev->channel = 0; + dev->op->config ( dev, NET80211_CFG_CHANNEL ); + + return ctx; +} + +/** + * Continue probe of 802.11 networks + * + * @v ctx Probe context returned by net80211_probe_start() + * @ret rc Probe status + * + * The return code will be 0 if the probe is still going on (and this + * function should be called again), a positive number if the probe + * completed successfully, or a negative error code if the probe + * failed for that reason. + * + * Whether the probe succeeded or failed, you must call + * net80211_probe_finish_all() or net80211_probe_finish_best() + * (depending on whether you want information on all networks or just + * the best-signal one) in order to release the probe context. A + * failed probe may still have acquired some valid data. + */ +int net80211_probe_step ( struct net80211_probe_ctx *ctx ) +{ + struct net80211_device *dev = ctx->dev; + u32 start_timeout = NET80211_PROBE_TIMEOUT * ticks_per_sec(); + u32 gather_timeout = ticks_per_sec(); + u32 now = currticks(); + struct io_buffer *iob; + int signal; + int rc; + char ssid[IEEE80211_MAX_SSID_LEN + 1]; + + gather_timeout *= ( ctx->essid[0] ? NET80211_PROBE_GATHER : + NET80211_PROBE_GATHER_ALL ); + + /* Time out if necessary */ + if ( now >= ctx->ticks_start + start_timeout ) + return list_empty ( ctx->beacons ) ? -ETIMEDOUT : +1; + + if ( ctx->ticks_beacon > 0 && now >= ctx->ticks_start + gather_timeout ) + return +1; + + /* Change channels if necessary */ + if ( now >= ctx->ticks_channel + ctx->hop_time ) { + dev->channel = ( dev->channel + ctx->hop_step ) + % dev->nr_channels; + dev->op->config ( dev, NET80211_CFG_CHANNEL ); + udelay ( dev->hw->channel_change_time ); + + ctx->ticks_channel = now; + + if ( ctx->probe ) { + struct io_buffer *siob = ctx->probe; /* to send */ + + /* make a copy for future use */ + iob = alloc_iob ( siob->tail - siob->head ); + iob_reserve ( iob, iob_headroom ( siob ) ); + memcpy ( iob_put ( iob, iob_len ( siob ) ), + siob->data, iob_len ( siob ) ); + + ctx->probe = iob; + rc = net80211_tx_mgmt ( dev, IEEE80211_STYPE_PROBE_REQ, + net80211_ll_broadcast, + iob_disown ( siob ) ); + if ( rc ) { + DBGC ( dev, "802.11 %p send probe failed: " + "%s\n", dev, strerror ( rc ) ); + return rc; + } + } + } + + /* Check for new management packets */ + while ( ( iob = net80211_mgmt_dequeue ( dev, &signal ) ) != NULL ) { + struct ieee80211_frame *hdr; + struct ieee80211_beacon *beacon; + union ieee80211_ie *ie; + struct net80211_wlan *wlan; + u16 type; + + hdr = iob->data; + type = hdr->fc & IEEE80211_FC_SUBTYPE; + beacon = ( struct ieee80211_beacon * ) hdr->data; + + if ( type != IEEE80211_STYPE_BEACON && + type != IEEE80211_STYPE_PROBE_RESP ) { + DBGC2 ( dev, "802.11 %p probe: non-beacon\n", dev ); + goto drop; + } + + if ( ( void * ) beacon->info_element >= iob->tail ) { + DBGC ( dev, "802.11 %p probe: beacon with no IEs\n", + dev ); + goto drop; + } + + ie = beacon->info_element; + while ( ie && ie->id != IEEE80211_IE_SSID ) + ie = ieee80211_next_ie ( ie, iob->tail ); + + if ( ! ie ) { + DBGC ( dev, "802.11 %p probe: beacon with no SSID\n", + dev ); + goto drop; + } + + memcpy ( ssid, ie->ssid, ie->len ); + ssid[ie->len] = 0; + + if ( ctx->essid[0] && strcmp ( ctx->essid, ssid ) != 0 ) { + DBGC2 ( dev, "802.11 %p probe: beacon with wrong SSID " + "(%s)\n", dev, ssid ); + goto drop; + } + + /* See if we've got an entry for this network */ + list_for_each_entry ( wlan, ctx->beacons, list ) { + if ( strcmp ( wlan->essid, ssid ) != 0 ) + continue; + + if ( signal < wlan->signal ) { + DBGC2 ( dev, "802.11 %p probe: beacon for %s " + "(%s) with weaker signal %d\n", dev, + ssid, eth_ntoa ( hdr->addr3 ), signal ); + goto drop; + } + + goto fill; + } + + /* No entry yet - make one */ + wlan = zalloc ( sizeof ( *wlan ) ); + strcpy ( wlan->essid, ssid ); + list_add_tail ( &wlan->list, ctx->beacons ); + + /* Whether we're using an old entry or a new one, fill + it with new data. */ + fill: + memcpy ( wlan->bssid, hdr->addr3, ETH_ALEN ); + wlan->signal = signal; + wlan->channel = dev->channels[dev->channel].channel_nr; + + /* Copy this I/O buffer into a new wlan->beacon; the + * iob we've got probably came from the device driver + * and may have the full 2.4k allocation, which we + * don't want to keep around wasting memory. + */ + free_iob ( wlan->beacon ); + wlan->beacon = alloc_iob ( iob_len ( iob ) ); + memcpy ( iob_put ( wlan->beacon, iob_len ( iob ) ), + iob->data, iob_len ( iob ) ); + + /* XXX actually check capab and RSN ie to + figure this out */ + wlan->handshaking = NET80211_SECPROT_NONE; + wlan->crypto = NET80211_CRYPT_NONE; + + ctx->ticks_beacon = now; + + DBGC2 ( dev, "802.11 %p probe: good beacon for %s (%s)\n", + dev, wlan->essid, eth_ntoa ( wlan->bssid ) ); + + drop: + free_iob ( iob ); + } + + return 0; +} + + +/** + * Finish probe of 802.11 networks, returning best-signal network found + * + * @v ctx Probe context + * @ret wlan Best-signal network found, or @c NULL if none were found + * + * If net80211_probe_start() was called with a particular SSID + * parameter as filter, only a network with that SSID (matching + * case-sensitively) can be returned from this function. + */ +struct net80211_wlan * +net80211_probe_finish_best ( struct net80211_probe_ctx *ctx ) +{ + struct net80211_wlan *best = NULL, *wlan; + + if ( ! ctx ) + return NULL; + + list_for_each_entry ( wlan, ctx->beacons, list ) { + if ( ! best || best->signal < wlan->signal ) + best = wlan; + } + + if ( best ) + list_del ( &best->list ); + else + DBGC ( ctx->dev, "802.11 %p probe: found nothing for '%s'\n", + ctx->dev, ctx->essid ); + + if ( ! list_empty ( ctx->beacons ) ) + net80211_free_wlanlist ( ctx->beacons ); + + net80211_keep_mgmt ( ctx->dev, ctx->old_keep_mgmt ); + + if ( ctx->probe ) + free_iob ( ctx->probe ); + + free ( ctx ); + + return best; +} + + +/** + * Finish probe of 802.11 networks, returning all networks found + * + * @v ctx Probe context + * @ret list List of net80211_wlan detailing networks found + * + * If net80211_probe_start() was called with a particular SSID + * parameter as filter, this will always return either an empty or a + * one-element list. + */ +struct list_head *net80211_probe_finish_all ( struct net80211_probe_ctx *ctx ) +{ + struct list_head *beacons = ctx->beacons; + + if ( ! ctx ) + return NULL; + + net80211_keep_mgmt ( ctx->dev, ctx->old_keep_mgmt ); + + if ( ctx->probe ) + free_iob ( ctx->probe ); + + free ( ctx ); + + return beacons; +} + + +/** + * Free WLAN structure + * + * @v wlan WLAN structure to free + */ +void net80211_free_wlan ( struct net80211_wlan *wlan ) +{ + if ( wlan ) { + free_iob ( wlan->beacon ); + free ( wlan ); + } +} + + +/** + * Free list of WLAN structures + * + * @v list List of WLAN structures to free + */ +void net80211_free_wlanlist ( struct list_head *list ) +{ + struct net80211_wlan *wlan, *tmp; + + if ( ! list ) + return; + + list_for_each_entry_safe ( wlan, tmp, list, list ) { + list_del ( &wlan->list ); + net80211_free_wlan ( wlan ); + } + + free ( list ); +} + + +/** Number of ticks to wait for replies to association management frames */ +#define ASSOC_TIMEOUT TICKS_PER_SEC + +/** Number of times to try sending a particular association management frame */ +#define ASSOC_RETRIES 2 + +/** + * Step 802.11 association process + * + * @v proc Association process + */ +static void net80211_step_associate ( struct process *proc ) +{ + struct net80211_device *dev = + container_of ( proc, struct net80211_device, proc_assoc ); + int rc = 0; + int status = dev->state & NET80211_STATUS_MASK; + + /* + * We use a sort of state machine implemented using bits in + * the dev->state variable. At each call, we take the + * logically first step that has not yet succeeded; either it + * has not been tried yet, it's being retried, or it failed. + * If it failed, we return an error indication; otherwise we + * perform the step. If it succeeds, RX handling code will set + * the appropriate status bit for us. + * + * Probe works a bit differently, since we have to step it + * on every call instead of waiting for a packet to arrive + * that will set the completion bit for us. + */ + + /* If we're waiting for a reply, check for timeout condition */ + if ( dev->state & NET80211_WAITING ) { + /* Sanity check */ + if ( ! dev->associating ) + return; + + if ( currticks() - dev->ctx.assoc->last_packet > ASSOC_TIMEOUT ) { + /* Timed out - fail if too many retries, or retry */ + dev->ctx.assoc->times_tried++; + if ( ++dev->ctx.assoc->times_tried > ASSOC_RETRIES ) { + rc = -ETIMEDOUT; + goto fail; + } + } else { + /* Didn't time out - let it keep going */ + return; + } + } else { + if ( dev->state & NET80211_PROBED ) + dev->ctx.assoc->times_tried = 0; + } + + if ( ! ( dev->state & NET80211_PROBED ) ) { + /* state: probe */ + + if ( ! dev->ctx.probe ) { + /* start probe */ + int active = fetch_intz_setting ( NULL, + &net80211_active_setting ); + int band = dev->hw->bands; + + if ( active ) + band &= ~NET80211_BAND_5GHZ; + + rc = net80211_prepare_probe ( dev, band, active ); + if ( rc ) + goto fail; + + dev->ctx.probe = net80211_probe_start ( dev, dev->essid, + active ); + if ( ! dev->ctx.probe ) { + dev->assoc_rc = -ENOMEM; + goto fail; + } + } + + rc = net80211_probe_step ( dev->ctx.probe ); + if ( ! rc ) { + return; /* still going */ + } + + dev->associating = net80211_probe_finish_best ( dev->ctx.probe ); + dev->ctx.probe = NULL; + if ( ! dev->associating ) { + if ( rc > 0 ) /* "successful" probe found nothing */ + rc = -ETIMEDOUT; + goto fail; + } + + /* If we probed using a broadcast SSID, record that + fact for the settings applicator before we clobber + it with the specific SSID we've chosen. */ + if ( ! dev->essid[0] ) + dev->state |= NET80211_AUTO_SSID; + + DBGC ( dev, "802.11 %p found network %s (%s)\n", dev, + dev->associating->essid, + eth_ntoa ( dev->associating->bssid ) ); + + dev->ctx.assoc = zalloc ( sizeof ( *dev->ctx.assoc ) ); + if ( ! dev->ctx.assoc ) { + rc = -ENOMEM; + goto fail; + } + + dev->state |= NET80211_PROBED; + dev->ctx.assoc->method = IEEE80211_AUTH_OPEN_SYSTEM; + + return; + } + + /* Record time of sending the packet we're about to send, for timeout */ + dev->ctx.assoc->last_packet = currticks(); + + if ( ! ( dev->state & NET80211_AUTHENTICATED ) ) { + /* state: prepare and authenticate */ + + if ( status != IEEE80211_STATUS_SUCCESS ) { + /* we tried authenticating already, but failed */ + int method = dev->ctx.assoc->method; + + if ( method == IEEE80211_AUTH_OPEN_SYSTEM && + ( status == IEEE80211_STATUS_AUTH_CHALL_INVALID || + status == IEEE80211_STATUS_AUTH_ALGO_UNSUPP ) ) { + /* Maybe this network uses Shared Key? */ + dev->ctx.assoc->method = + IEEE80211_AUTH_SHARED_KEY; + } else { + goto fail; + } + } + + DBGC ( dev, "802.11 %p authenticating with method %d\n", dev, + dev->ctx.assoc->method ); + + rc = net80211_prepare_assoc ( dev, dev->associating ); + if ( rc ) + goto fail; + + rc = net80211_send_auth ( dev, dev->associating, + dev->ctx.assoc->method ); + if ( rc ) + goto fail; + + return; + } + + if ( ! ( dev->state & NET80211_ASSOCIATED ) ) { + /* state: associate */ + + if ( status != IEEE80211_STATUS_SUCCESS ) + goto fail; + + DBGC ( dev, "802.11 %p associating\n", dev ); + + rc = net80211_send_assoc ( dev, dev->associating ); + if ( rc ) + goto fail; + + return; + } + + if ( ! ( dev->state & NET80211_CRYPTO_SYNCED ) ) { + /* state: crypto sync */ + DBGC ( dev, "802.11 %p security handshaking\n", dev ); + + dev->state |= NET80211_CRYPTO_SYNCED; + /* XXX need to actually do something here once we + support WPA */ + return; + } + + /* state: done! */ + netdev_link_up ( dev->netdev ); + dev->assoc_rc = 0; + dev->state &= ~NET80211_WORKING; + + free ( dev->ctx.assoc ); + dev->ctx.assoc = NULL; + + net80211_free_wlan ( dev->associating ); + dev->associating = NULL; + + dev->rctl = rc80211_init ( dev ); + + process_del ( proc ); + + DBGC ( dev, "802.11 %p associated with %s (%s)\n", dev, + dev->essid, eth_ntoa ( dev->bssid ) ); + + return; + + fail: + dev->state &= ~( NET80211_WORKING | NET80211_WAITING ); + if ( rc ) + dev->assoc_rc = rc; + + netdev_link_err ( dev->netdev, dev->assoc_rc ); + + /* We never reach here from the middle of a probe, so we don't + need to worry about freeing dev->ctx.probe. */ + + if ( dev->state & NET80211_PROBED ) { + free ( dev->ctx.assoc ); + dev->ctx.assoc = NULL; + } + + net80211_free_wlan ( dev->associating ); + dev->associating = NULL; + + process_del ( proc ); + + DBGC ( dev, "802.11 %p association failed (state=%04x): " + "%s\n", dev, dev->state, strerror ( dev->assoc_rc ) ); + + /* Try it again: */ + net80211_autoassociate ( dev ); +} + +/** + * Check for 802.11 SSID updates + * + * This acts as a settings applicator; if the user changes netX/ssid, + * and netX is currently open, the association task will be invoked + * again. + */ +static int net80211_check_ssid_update ( void ) +{ + struct net80211_device *dev; + char ssid[IEEE80211_MAX_SSID_LEN + 1]; + + list_for_each_entry ( dev, &net80211_devices, list ) { + if ( ! ( dev->netdev->state & NETDEV_OPEN ) ) + continue; + + fetch_string_setting ( netdev_settings ( dev->netdev ), + &net80211_ssid_setting, ssid, + IEEE80211_MAX_SSID_LEN + 1 ); + + if ( strcmp ( ssid, dev->essid ) != 0 && + ! ( ! ssid[0] && ( dev->state & NET80211_AUTO_SSID ) ) ) { + DBGC ( dev, "802.11 %p updating association: " + "%s -> %s\n", dev, dev->essid, ssid ); + net80211_autoassociate ( dev ); + } + } + + return 0; +} + +/** + * Start 802.11 association process + * + * @v dev 802.11 device + * + * If the association process is running, it will be restarted. + */ +void net80211_autoassociate ( struct net80211_device *dev ) +{ + if ( ! ( dev->state & NET80211_WORKING ) ) { + DBGC2 ( dev, "802.11 %p spawning association process\n", dev ); + process_add ( &dev->proc_assoc ); + } + + /* Clean up everything an earlier association process might + have been in the middle of using */ + if ( dev->associating ) + net80211_free_wlan ( dev->associating ); + + if ( ! ( dev->state & NET80211_PROBED ) ) + net80211_free_wlan ( + net80211_probe_finish_best ( dev->ctx.probe ) ); + else + free ( dev->ctx.assoc ); + + /* Reset to a clean state */ + fetch_string_setting ( netdev_settings ( dev->netdev ), + &net80211_ssid_setting, dev->essid, + IEEE80211_MAX_SSID_LEN + 1 ); + dev->ctx.probe = NULL; + dev->associating = NULL; + net80211_set_state ( dev, NET80211_PROBED, NET80211_WORKING, 0 ); +} + +/** + * Pick TX rate for RTS/CTS packets based on data rate + * + * @v dev 802.11 device + * + * The RTS/CTS rate is the fastest TX rate marked as "basic" that is + * not faster than the data rate. + */ +static void net80211_set_rtscts_rate ( struct net80211_device *dev ) +{ + u16 datarate = dev->rates[dev->rate]; + u16 rtsrate = 0; + int rts_idx = -1; + int i; + + for ( i = 0; i < dev->nr_rates; i++ ) { + u16 rate = dev->rates[i]; + + if ( ! ( dev->basic_rates & ( 1 << i ) ) || rate > datarate ) + continue; + + if ( rate > rtsrate ) { + rtsrate = rate; + rts_idx = i; + } + } + + /* If this is in initialization, we might not have any basic + rates; just use the first data rate in that case. */ + if ( rts_idx < 0 ) + rts_idx = 0; + + dev->rtscts_rate = rts_idx; +} + +/** + * Set data transmission rate for 802.11 device + * + * @v dev 802.11 device + * @v rate Rate to set, as index into @c dev->rates array + */ +void net80211_set_rate_idx ( struct net80211_device *dev, int rate ) +{ + assert ( dev->netdev->state & NETDEV_OPEN ); + + if ( rate >= 0 && rate < dev->nr_rates && rate != dev->rate ) { + DBGC2 ( dev, "802.11 %p changing rate from %d->%d Mbps\n", + dev, dev->rates[dev->rate] / 10, + dev->rates[rate] / 10 ); + + dev->rate = rate; + net80211_set_rtscts_rate ( dev ); + dev->op->config ( dev, NET80211_CFG_RATE ); + } +} + +/** + * Configure 802.11 device to transmit on a certain channel + * + * @v dev 802.11 device + * @v channel Channel number (1-11 for 2.4GHz) to transmit on + */ +int net80211_change_channel ( struct net80211_device *dev, int channel ) +{ + int i, oldchan = dev->channel; + + assert ( dev->netdev->state & NETDEV_OPEN ); + + for ( i = 0; i < dev->nr_channels; i++ ) { + if ( dev->channels[i].channel_nr == channel ) { + dev->channel = i; + break; + } + } + + if ( i == dev->nr_channels ) + return -ENOENT; + + if ( i != oldchan ) + return dev->op->config ( dev, NET80211_CFG_CHANNEL ); + + return 0; +} + +/** + * Prepare 802.11 device channel and rate set for scanning + * + * @v dev 802.11 device + * @v band RF band(s) on which to prepare for scanning + * @v active Whether the scanning will be active + * @ret rc Return status code + */ +int net80211_prepare_probe ( struct net80211_device *dev, int band, + int active ) +{ + assert ( dev->netdev->state & NETDEV_OPEN ); + + if ( active && band != NET80211_BAND_2GHZ ) { + DBGC ( dev, "802.11 %p cannot perform active scanning on " + "5GHz band\n", dev ); + return -EINVAL_ACTIVE_SCAN; + } + + if ( band == 0 ) { + /* This can happen for a 5GHz-only card with 5GHz + scanning masked out by an active request. */ + DBGC ( dev, "802.11 %p asked to prepare for scanning nothing\n", + dev ); + return -EINVAL_ACTIVE_SCAN; + } + + dev->nr_channels = 0; + + if ( active ) + net80211_add_channels ( dev, 1, 11, NET80211_REG_TXPOWER ); + else { + if ( band & NET80211_BAND_2GHZ ) + net80211_add_channels ( dev, 1, 14, + NET80211_REG_TXPOWER ); + if ( band & NET80211_BAND_5GHZ ) + net80211_add_channels ( dev, 36, 8, + NET80211_REG_TXPOWER ); + } + + /* Use channel 1 for now */ + dev->channel = 0; + dev->op->config ( dev, NET80211_CFG_CHANNEL ); + + /* Always do active probes at 1Mbps */ + dev->rate = 0; + dev->nr_rates = 1; + dev->rates[0] = 10; + dev->op->config ( dev, NET80211_CFG_RATE ); + + return 0; +} + +/** + * Prepare 802.11 device channel and rate set for communication + * + * @v dev 802.11 device + * @v wlan WLAN to prepare for communication with + * @ret rc Return status code + */ +int net80211_prepare_assoc ( struct net80211_device *dev, + struct net80211_wlan *wlan ) +{ + struct ieee80211_frame *hdr = wlan->beacon->data; + struct ieee80211_beacon *beacon = + ( struct ieee80211_beacon * ) hdr->data; + int rc; + + assert ( dev->netdev->state & NETDEV_OPEN ); + + net80211_set_state ( dev, NET80211_ASSOCIATED, 0, 0 ); + memcpy ( dev->bssid, wlan->bssid, ETH_ALEN ); + strcpy ( dev->essid, wlan->essid ); + + dev->last_beacon_timestamp = beacon->timestamp; + dev->tx_beacon_interval = 1024 * beacon->beacon_interval; + + /* XXX do crypto setup here */ + + /* Barring an IE that tells us the channel outright, assume + the channel we heard this AP best on is the channel it's + communicating on. */ + net80211_change_channel ( dev, wlan->channel ); + + rc = net80211_process_capab ( dev, beacon->capability ); + if ( rc ) + return rc; + + rc = net80211_process_ie ( dev, beacon->info_element, + wlan->beacon->tail ); + if ( rc ) + return rc; + + /* Associate at the lowest rate so we know it'll get through */ + dev->rate = 0; + dev->op->config ( dev, NET80211_CFG_RATE ); + + return 0; +} + +/** + * Send 802.11 initial authentication frame + * + * @v dev 802.11 device + * @v wlan WLAN to authenticate with + * @v method Authentication method + * @ret rc Return status code + * + * @a method may be 0 for Open System authentication or 1 for Shared + * Key authentication. Open System provides no security in association + * whatsoever, relying on encryption for confidentiality, but Shared + * Key actively introduces security problems and is very rarely used. + */ +int net80211_send_auth ( struct net80211_device *dev, + struct net80211_wlan *wlan, int method ) +{ + struct io_buffer *iob = alloc_iob ( 64 ); + struct ieee80211_auth *auth; + + net80211_set_state ( dev, 0, NET80211_WAITING, 0 ); + iob_reserve ( iob, IEEE80211_TYP_FRAME_HEADER_LEN ); + auth = iob_put ( iob, sizeof ( *auth ) ); + auth->algorithm = method; + auth->tx_seq = 1; + auth->status = 0; + + return net80211_tx_mgmt ( dev, IEEE80211_STYPE_AUTH, wlan->bssid, iob ); +} + +/** + * Handle receipt of 802.11 authentication frame + * + * @v dev 802.11 device + * @v iob I/O buffer + * + * If the authentication method being used is Shared Key, and the + * frame that was received included challenge text, the frame is + * encrypted using the cryptographic algorithm currently in effect and + * sent back to the AP to complete the authentication. + */ +static void net80211_handle_auth ( struct net80211_device *dev, + struct io_buffer *iob ) +{ + struct ieee80211_frame *hdr = iob->data; + struct ieee80211_auth *auth = + ( struct ieee80211_auth * ) hdr->data; + + if ( auth->tx_seq & 1 ) { + DBGC ( dev, "802.11 %p authentication received improperly " + "directed frame (seq. %d)\n", dev, auth->tx_seq ); + net80211_set_state ( dev, NET80211_WAITING, 0, + IEEE80211_STATUS_FAILURE ); + return; + } + + if ( auth->status != IEEE80211_STATUS_SUCCESS ) { + DBGC ( dev, "802.11 %p authentication failed: status %d\n", + dev, auth->status ); + net80211_set_state ( dev, NET80211_WAITING, 0, + auth->status ); + return; + } + + if ( auth->algorithm == IEEE80211_AUTH_SHARED_KEY && ! dev->crypto ) { + DBGC ( dev, "802.11 %p can't perform shared-key authentication " + "without a cryptosystem\n", dev ); + net80211_set_state ( dev, NET80211_WAITING, 0, + IEEE80211_STATUS_FAILURE ); + return; + } + + if ( auth->algorithm == IEEE80211_AUTH_SHARED_KEY && + auth->tx_seq == 2 ) { + /* Since the iob we got is going to be freed as soon + as we return, we can do some in-place + modification. */ + auth->tx_seq = 3; + auth->status = 0; + + memcpy ( hdr->addr2, hdr->addr1, ETH_ALEN ); + memcpy ( hdr->addr1, hdr->addr3, ETH_ALEN ); + + netdev_tx ( dev->netdev, + dev->crypto->encrypt ( dev->crypto, iob ) ); + return; + } + + net80211_set_state ( dev, NET80211_WAITING, NET80211_AUTHENTICATED, + IEEE80211_STATUS_SUCCESS ); + + return; +} + +/** + * Send 802.11 association frame + * + * @v dev 802.11 device + * @v wlan WLAN to associate with + * @ret rc Return status code + */ +int net80211_send_assoc ( struct net80211_device *dev, + struct net80211_wlan *wlan ) +{ + struct io_buffer *iob = alloc_iob ( 128 ); + struct ieee80211_assoc_req *assoc; + union ieee80211_ie *ie; + + net80211_set_state ( dev, 0, NET80211_WAITING, 0 ); + + iob_reserve ( iob, IEEE80211_TYP_FRAME_HEADER_LEN ); + assoc = iob->data; + + assoc->capability = IEEE80211_CAPAB_MANAGED; + if ( ! ( dev->hw->flags & NET80211_HW_NO_SHORT_PREAMBLE ) ) + assoc->capability |= IEEE80211_CAPAB_SHORT_PMBL; + if ( ! ( dev->hw->flags & NET80211_HW_NO_SHORT_SLOT ) ) + assoc->capability |= IEEE80211_CAPAB_SHORT_SLOT; + if ( wlan->crypto ) + assoc->capability |= IEEE80211_CAPAB_PRIVACY; + + assoc->listen_interval = 1; + + ie = net80211_marshal_request_info ( dev, assoc->info_element ); + + DBGP ( "802.11 %p about to send association request:\n", dev ); + DBGP_HD ( iob->data, ( void * ) ie - iob->data ); + + /* XXX add RSN ie for WPA support */ + + iob_put ( iob, ( void * ) ie - iob->data ); + + return net80211_tx_mgmt ( dev, IEEE80211_STYPE_ASSOC_REQ, + wlan->bssid, iob ); +} + +/** + * Handle receipt of 802.11 association reply frame + * + * @v dev 802.11 device + * @v iob I/O buffer + */ +static void net80211_handle_assoc_reply ( struct net80211_device *dev, + struct io_buffer *iob ) +{ + struct ieee80211_frame *hdr = iob->data; + struct ieee80211_assoc_resp *assoc = + ( struct ieee80211_assoc_resp * ) hdr->data; + + net80211_process_capab ( dev, assoc->capability ); + net80211_process_ie ( dev, assoc->info_element, iob->tail ); + + if ( assoc->status != IEEE80211_STATUS_SUCCESS ) { + DBGC ( dev, "802.11 %p association failed: status %d\n", + dev, assoc->status ); + net80211_set_state ( dev, NET80211_WAITING, 0, + assoc->status ); + return; + } + + /* ESSID was filled before the association request was sent */ + memcpy ( dev->bssid, hdr->addr3, ETH_ALEN ); + dev->aid = assoc->aid; + + net80211_set_state ( dev, NET80211_WAITING, NET80211_ASSOCIATED, + IEEE80211_STATUS_SUCCESS ); +} + + +/** + * Send 802.11 disassociation frame + * + * @v dev 802.11 device + * @v reason Reason for disassociation + * @ret rc Return status code + */ +static int net80211_send_disassoc ( struct net80211_device *dev, int reason ) +{ + struct io_buffer *iob = alloc_iob ( 64 ); + struct ieee80211_disassoc *disassoc; + + if ( ! ( dev->state & NET80211_ASSOCIATED ) ) + return -EINVAL; + + net80211_set_state ( dev, NET80211_ASSOCIATED, 0, 0 ); + iob_reserve ( iob, IEEE80211_TYP_FRAME_HEADER_LEN ); + disassoc = iob_put ( iob, sizeof ( *disassoc ) ); + disassoc->reason = reason; + + return net80211_tx_mgmt ( dev, IEEE80211_STYPE_DISASSOC, dev->bssid, + iob ); +} + + +/** Smoothing factor (1-7) for link quality calculation */ +#define LQ_SMOOTH 7 + +/** + * Update link quality information based on received beacon + * + * @v dev 802.11 device + * @v iob I/O buffer containing beacon + * @ret rc Return status code + */ +static void net80211_update_link_quality ( struct net80211_device *dev, + struct io_buffer *iob ) +{ + struct ieee80211_frame *hdr = iob->data; + struct ieee80211_beacon *beacon; + u32 dt, rxi; + + if ( ! ( dev->state & NET80211_ASSOCIATED ) ) + return; + + beacon = ( struct ieee80211_beacon * ) hdr->data; + dt = ( u32 ) ( beacon->timestamp - dev->last_beacon_timestamp ); + rxi = dev->rx_beacon_interval; + + rxi = ( LQ_SMOOTH * rxi ) + ( ( 8 - LQ_SMOOTH ) * dt ); + dev->rx_beacon_interval = rxi >> 3; + + dev->last_beacon_timestamp = beacon->timestamp; +} + + +/** + * Handle receipt of 802.11 management frame + * + * @v dev 802.11 device + * @v iob I/O buffer + * @v signal Signal strength of received frame + */ +static void net80211_handle_mgmt ( struct net80211_device *dev, + struct io_buffer *iob, int signal ) +{ + struct ieee80211_frame *hdr = iob->data; + struct ieee80211_disassoc *disassoc; + u16 stype = hdr->fc & IEEE80211_FC_SUBTYPE; + int keep = 0; + int is_deauth = ( stype == IEEE80211_STYPE_DEAUTH ); + + if ( ( hdr->fc & IEEE80211_FC_TYPE ) != IEEE80211_TYPE_MGMT ) { + free_iob ( iob ); + return; /* only handle management frames */ + } + + switch ( stype ) { + /* We reconnect on deauthentication and disassociation. */ + case IEEE80211_STYPE_DEAUTH: + case IEEE80211_STYPE_DISASSOC: + disassoc = ( struct ieee80211_disassoc * ) hdr->data; + net80211_set_state ( dev, is_deauth ? NET80211_AUTHENTICATED : + NET80211_ASSOCIATED, 0, + NET80211_IS_REASON | disassoc->reason ); + DBGC ( dev, "802.11 %p %s: reason %d\n", + dev, is_deauth ? "deauthenticated" : "disassociated", + disassoc->reason ); + + /* Try to reassociate, in case it's transient. */ + net80211_autoassociate ( dev ); + + break; + + /* We handle authentication and association. */ + case IEEE80211_STYPE_AUTH: + if ( ! ( dev->state & NET80211_AUTHENTICATED ) ) + net80211_handle_auth ( dev, iob ); + break; + + case IEEE80211_STYPE_ASSOC_RESP: + case IEEE80211_STYPE_REASSOC_RESP: + if ( ! ( dev->state & NET80211_ASSOCIATED ) ) + net80211_handle_assoc_reply ( dev, iob ); + break; + + /* We pass probes and beacons onto network scanning + code. Pass actions for future extensibility. */ + case IEEE80211_STYPE_BEACON: + net80211_update_link_quality ( dev, iob ); + /* fall through */ + case IEEE80211_STYPE_PROBE_RESP: + case IEEE80211_STYPE_ACTION: + if ( dev->keep_mgmt ) { + struct net80211_rx_info *rxinf; + rxinf = zalloc ( sizeof ( *rxinf ) ); + if ( ! rxinf ) { + DBGC ( dev, "802.11 %p out of memory\n", dev ); + break; + } + rxinf->signal = signal; + list_add_tail ( &iob->list, &dev->mgmt_queue ); + list_add_tail ( &rxinf->list, &dev->mgmt_info_queue ); + keep = 1; + } + break; + + case IEEE80211_STYPE_PROBE_REQ: + /* Some nodes send these broadcast. Ignore them. */ + break; + + case IEEE80211_STYPE_ASSOC_REQ: + case IEEE80211_STYPE_REASSOC_REQ: + /* We should never receive these, only send them. */ + DBGC ( dev, "802.11 %p received strange management request " + "(%04x)\n", dev, stype ); + break; + + default: + DBGC ( dev, "802.11 %p received unimplemented management " + "packet (%04x)\n", dev, stype ); + break; + } + + if ( ! keep ) + free_iob ( iob ); +} + +/* ---------- Packet handling functions ---------- */ + +/** + * Free buffers used by 802.11 fragment cache entry + * + * @v dev 802.11 device + * @v fcid Fragment cache entry index + * + * After this function, the referenced entry will be marked unused. + */ +static void net80211_free_frags ( struct net80211_device *dev, int fcid ) +{ + int j; + struct net80211_frag_cache *frag = &dev->frags[fcid]; + + for ( j = 0; j < 16; j++ ) { + if ( frag->iob[j] ) { + free_iob ( frag->iob[j] ); + frag->iob[j] = NULL; + } + } + + frag->seqnr = 0; + frag->start_ticks = 0; + frag->in_use = 0; +} + +/** + * Accumulate 802.11 fragments into one I/O buffer + * + * @v dev 802.11 device + * @v fcid Fragment cache entry index + * @v nfrags Number of fragments received + * @v size Sum of sizes of all fragments, including headers + * @ret iob I/O buffer containing reassembled packet + * + * This function does not free the fragment buffers. + */ +static struct io_buffer *net80211_accum_frags ( struct net80211_device *dev, + int fcid, int nfrags, int size ) +{ + struct net80211_frag_cache *frag = &dev->frags[fcid]; + int hdrsize = IEEE80211_TYP_FRAME_HEADER_LEN; + int nsize = size - hdrsize * ( nfrags - 1 ); + int i; + + struct io_buffer *niob = alloc_iob ( nsize ); + struct ieee80211_frame *hdr; + + /* Add the header from the first one... */ + memcpy ( iob_put ( niob, hdrsize ), frag->iob[0]->data, hdrsize ); + + /* ... and all the data from all of them. */ + for ( i = 0; i < nfrags; i++ ) { + int len = iob_len ( frag->iob[i] ) - hdrsize; + memcpy ( iob_put ( niob, len ), + frag->iob[i]->data + hdrsize, len ); + } + + /* Turn off the fragment bit. */ + hdr = niob->data; + hdr->fc &= ~IEEE80211_FC_MORE_FRAG; + + return niob; +} + +/** + * Handle receipt of 802.11 fragment + * + * @v dev 802.11 device + * @v iob I/O buffer containing fragment + * @v signal Signal strength with which fragment was received + */ +static void net80211_rx_frag ( struct net80211_device *dev, + struct io_buffer *iob, int signal ) +{ + struct ieee80211_frame *hdr = iob->data; + int fragnr = IEEE80211_FRAG ( hdr->seq ); + + if ( fragnr == 0 && ( hdr->fc & IEEE80211_FC_MORE_FRAG ) ) { + /* start a frag cache entry */ + int i, newest = -1; + u32 curr_ticks = currticks(), newest_ticks = 0; + u32 timeout = ticks_per_sec() * NET80211_FRAG_TIMEOUT; + + for ( i = 0; i < NET80211_NR_CONCURRENT_FRAGS; i++ ) { + if ( dev->frags[i].in_use == 0 ) + break; + + if ( dev->frags[i].start_ticks + timeout >= + curr_ticks ) { + net80211_free_frags ( dev, i ); + break; + } + + if ( dev->frags[i].start_ticks > newest_ticks ) { + newest = i; + newest_ticks = dev->frags[i].start_ticks; + } + } + + /* If we're being sent more concurrent fragmented + packets than we can handle, drop the newest so the + older ones have time to complete. */ + if ( i == NET80211_NR_CONCURRENT_FRAGS ) { + i = newest; + net80211_free_frags ( dev, i ); + } + + dev->frags[i].in_use = 1; + dev->frags[i].seqnr = IEEE80211_SEQNR ( hdr->seq ); + dev->frags[i].start_ticks = currticks(); + dev->frags[i].iob[0] = iob; + return; + } else { + int i; + for ( i = 0; i < NET80211_NR_CONCURRENT_FRAGS; i++ ) { + if ( dev->frags[i].in_use && dev->frags[i].seqnr == + IEEE80211_SEQNR ( hdr->seq ) ) + break; + } + if ( i == NET80211_NR_CONCURRENT_FRAGS ) { + /* Drop non-first not-in-cache fragments */ + DBGC ( dev, "802.11 %p dropped fragment fc=%04x " + "seq=%04x\n", dev, hdr->fc, hdr->seq ); + free_iob ( iob ); + return; + } + + dev->frags[i].iob[fragnr] = iob; + + if ( ! ( hdr->fc & IEEE80211_FC_MORE_FRAG ) ) { + int j, size = 0; + for ( j = 0; j < fragnr; j++ ) { + size += iob_len ( dev->frags[i].iob[j] ); + if ( dev->frags[i].iob[j] == NULL ) + break; + } + if ( j == fragnr ) { + /* We've got everything */ + struct io_buffer *niob = + net80211_accum_frags ( dev, i, fragnr, + size ); + net80211_free_frags ( dev, i ); + net80211_rx ( dev, niob, signal, 0 ); + } else { + DBGC ( dev, "802.11 %p dropping fragmented " + "packet due to out-of-order arrival, " + "fc=%04x seq=%04x\n", dev, hdr->fc, + hdr->seq ); + net80211_free_frags ( dev, i ); + } + } + } +} + +/** + * Handle receipt of 802.11 frame + * + * @v dev 802.11 device + * @v iob I/O buffer + * @v signal Received signal strength + * @v rate Bitrate at which frame was received, in 100 kbps units + * + * If the rate or signal is unknown, 0 should be passed. + */ +void net80211_rx ( struct net80211_device *dev, struct io_buffer *iob, + int signal, u16 rate ) +{ + struct ieee80211_frame *hdr = iob->data; + u16 type = hdr->fc & IEEE80211_FC_TYPE; + if ( ( hdr->fc & IEEE80211_FC_VERSION ) != IEEE80211_THIS_VERSION ) + goto drop; /* drop invalid-version packets */ + + if ( type == IEEE80211_TYPE_CTRL ) + goto drop; /* we don't handle control packets, + the hardware does */ + + if ( dev->last_rx_seq == hdr->seq ) + goto drop; /* avoid duplicate packet */ + dev->last_rx_seq = hdr->seq; + + if ( dev->hw->flags & NET80211_HW_RX_HAS_FCS ) { + /* discard the FCS */ + iob_unput ( iob, 4 ); + } + + if ( hdr->fc & IEEE80211_FC_PROTECTED ) { + struct io_buffer *niob; + if ( ! dev->crypto ) + goto drop; /* can't decrypt packets on an open network */ + + niob = dev->crypto->decrypt ( dev->crypto, iob ); + if ( ! niob ) + goto drop; /* drop failed decryption */ + free_iob ( iob ); + iob = niob; + } + + dev->last_signal = signal; + + /* Fragments go into the frag cache or get dropped. */ + if ( IEEE80211_FRAG ( hdr->seq ) != 0 + || ( hdr->fc & IEEE80211_FC_MORE_FRAG ) ) { + net80211_rx_frag ( dev, iob, signal ); + return; + } + + /* Management frames get handled, enqueued, or dropped. */ + if ( type == IEEE80211_TYPE_MGMT ) { + net80211_handle_mgmt ( dev, iob, signal ); + return; + } + + /* Data frames get dropped or sent to the net_device. */ + if ( ( hdr->fc & IEEE80211_FC_SUBTYPE ) != IEEE80211_STYPE_DATA ) + goto drop; /* drop QoS, CFP, or null data packets */ + + /* Update rate-control algorithm */ + if ( dev->rctl ) + rc80211_update_rx ( dev, hdr->fc & IEEE80211_FC_RETRY, rate ); + + /* Pass packet onward */ + if ( netdev_link_ok ( dev->netdev ) ) { + netdev_rx ( dev->netdev, iob ); + return; + } + + drop: + DBGC2 ( dev, "802.11 %p dropped packet fc=%04x seq=%04x\n", dev, + hdr->fc, hdr->seq ); + free_iob ( iob ); + return; +} + +/** Indicate an error in receiving a packet + * + * @v dev 802.11 device + * @v iob I/O buffer with received packet, or NULL + * @v rc Error code + * + * This logs the error with the wrapping net_device, and frees iob if + * it is passed. + */ +void net80211_rx_err ( struct net80211_device *dev, + struct io_buffer *iob, int rc ) +{ + netdev_rx_err ( dev->netdev, iob, rc ); +} + +/** Indicate the completed transmission of a packet + * + * @v dev 802.11 device + * @v iob I/O buffer of transmitted packet + * @v retries Number of times this packet was retransmitted + * @v rc Error code, or 0 for success + * + * This logs an error with the wrapping net_device if one occurred, + * and removes and frees the I/O buffer from its TX queue. The + * provided retry information is used to tune our transmission rate. + * + * If the packet did not need to be retransmitted because it was + * properly ACKed the first time, @a retries should be 0. + */ +void net80211_tx_complete ( struct net80211_device *dev, + struct io_buffer *iob, int retries, int rc ) +{ + /* Update rate-control algorithm */ + if ( dev->rctl ) + rc80211_update_tx ( dev, retries, rc ); + + /* Pass completion onward */ + netdev_tx_complete_err ( dev->netdev, iob, rc ); +} diff --git a/src/net/80211/rc80211.c b/src/net/80211/rc80211.c new file mode 100644 index 00000000..5bd19143 --- /dev/null +++ b/src/net/80211/rc80211.c @@ -0,0 +1,371 @@ +/* + * Simple 802.11 rate-control algorithm for gPXE. + * + * Copyright (c) 2009 Joshua Oreman <oremanj@rwcr.net>. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or any later version. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. + */ + +FILE_LICENCE ( GPL2_OR_LATER ); + +#include <stdlib.h> +#include <gpxe/net80211.h> + +/** + * @file + * + * Simple 802.11 rate-control algorithm + */ + +/** @page rc80211 Rate control philosophy + * + * We want to maximize our transmission speed, to the extent that we + * can do that without dropping undue numbers of packets. We also + * don't want to take up very much code space, so our algorithm has to + * be pretty simple + * + * When we receive a packet, we know what rate it was transmitted at, + * and whether it had to be retransmitted to get to us. + * + * When we send a packet, we hear back how many times it had to be + * retried to get through, and whether it got through at all. + * + * Indications of TX success are more reliable than RX success, but RX + * information helps us know where to start. + * + * To handle all of this, we keep for each rate and each direction (TX + * and RX separately) some state information for the most recent + * packets on that rate and the number of packets for which we have + * information. The state is a 32-bit unsigned integer in which two + * bits represent a packet: 11 if it went through well, 10 if it went + * through with one retry, 01 if it went through with more than one + * retry, or 00 if it didn't go through at all. We define the + * "goodness" for a particular (rate, direction) combination as the + * sum of all the 2-bit fields, times 33, divided by the number of + * 2-bit fields containing valid information (16 except when we're + * starting out). The number produced is between 0 and 99; we use -1 + * for rates with less than 4 RX packets or 1 TX, as an indicator that + * we do not have enough information to rely on them. + * + * In deciding which rates are best, we find the weighted average of + * TX and RX goodness, where the weighting is by number of packets + * with data and TX packets are worth 4 times as much as RX packets. + * The weighted average is called "net goodness" and is also a number + * between 0 and 99. If 3 consecutive packets fail transmission + * outright, we automatically ratchet down the rate; otherwise, we + * switch to the best rate whenever the current rate's goodness falls + * below some threshold, and try increasing our rate when the goodness + * is very high. + * + * This system is optimized for gPXE's style of usage. Because normal + * operation always involves receiving something, we'll make our way + * to the best rate pretty quickly. We tend to follow the lead of the + * sending AP in choosing rates, but we won't use rates for long that + * don't work well for us in transmission. We assume gPXE won't be + * running for long enough that rate patterns will change much, so we + * don't have to keep time counters or the like. And if this doesn't + * work well in practice there are many ways it could be tweaked. + * + * To avoid staying at 1Mbps for a long time, we don't track any + * transmitted packets until we've set our rate based on received + * packets. + */ + +/** Two-bit packet status indicator for a packet with no retries */ +#define RC_PKT_OK 0x3 + +/** Two-bit packet status indicator for a packet with one retry */ +#define RC_PKT_RETRIED_ONCE 0x2 + +/** Two-bit packet status indicator for a TX packet with multiple retries + * + * It is not possible to tell whether an RX packet had one or multiple + * retries; we rely instead on the fact that failed RX packets won't + * get to us at all, so if we receive a lot of RX packets on a certain + * rate it must be pretty good. + */ +#define RC_PKT_RETRIED_MULTI 0x1 + +/** Two-bit packet status indicator for a TX packet that was never ACKed + * + * It is not possible to tell whether an RX packet was setn if it + * didn't get through to us, but if we don't see one we won't increase + * the goodness for its rate. This asymmetry is part of why TX packets + * are weighted much more heavily than RX. + */ +#define RC_PKT_FAILED 0x0 + +/** Number of times to weight TX packets more heavily than RX packets */ +#define RC_TX_FACTOR 4 + +/** Number of consecutive failed TX packets that cause an automatic rate drop */ +#define RC_TX_EMERG_FAIL 3 + +/** Minimum net goodness below which we will search for a better rate */ +#define RC_GOODNESS_MIN 85 + +/** Maximum net goodness above which we will try to increase our rate */ +#define RC_GOODNESS_MAX 95 + +/** Minimum (num RX + @c RC_TX_FACTOR * num TX) to use a certain rate */ +#define RC_UNCERTAINTY_THRESH 4 + +/** TX direction */ +#define TX 0 + +/** RX direction */ +#define RX 1 + +/** A rate control context */ +struct rc80211_ctx +{ + /** Goodness state for each rate, TX and RX */ + u32 goodness[2][NET80211_MAX_RATES]; + + /** Number of packets recorded for each rate */ + u8 count[2][NET80211_MAX_RATES]; + + /** Indication of whether we've set the device rate yet */ + int started; + + /** Counter of all packets sent and received */ + int packets; +}; + +/** + * Initialize rate-control algorithm + * + * @v dev 802.11 device + * @ret ctx Rate-control context, to be stored in @c dev->rctl + */ +struct rc80211_ctx * rc80211_init ( struct net80211_device *dev __unused ) +{ + struct rc80211_ctx *ret = zalloc ( sizeof ( *ret ) ); + return ret; +} + +/** + * Calculate net goodness for a certain rate + * + * @v ctx Rate-control context + * @v rate_idx Index of rate to calculate net goodness for + */ +static int rc80211_calc_net_goodness ( struct rc80211_ctx *ctx, + int rate_idx ) +{ + int sum[2], num[2], dir, pkt; + + for ( dir = 0; dir < 2; dir++ ) { + u32 good = ctx->goodness[dir][rate_idx]; + + num[dir] = ctx->count[dir][rate_idx]; + sum[dir] = 0; + + for ( pkt = 0; pkt < num[dir]; pkt++ ) + sum[dir] += ( good >> ( 2 * pkt ) ) & 0x3; + } + + if ( ( num[TX] * RC_TX_FACTOR + num[RX] ) < RC_UNCERTAINTY_THRESH ) + return -1; + + return ( 33 * ( sum[TX] * RC_TX_FACTOR + sum[RX] ) / + ( num[TX] * RC_TX_FACTOR + num[RX] ) ); +} + +/** + * Determine the best rate to switch to and return it + * + * @v dev 802.11 device + * @ret rate_idx Index of the best rate to switch to + */ +static int rc80211_pick_best ( struct net80211_device *dev ) +{ + struct rc80211_ctx *ctx = dev->rctl; + int best_net_good = 0, best_rate = -1, i; + + for ( i = 0; i < dev->nr_rates; i++ ) { + int net_good = rc80211_calc_net_goodness ( ctx, i ); + + if ( net_good > best_net_good || + ( best_net_good > RC_GOODNESS_MIN && + net_good > RC_GOODNESS_MIN ) ) { + best_net_good = net_good; + best_rate = i; + } + } + + if ( best_rate >= 0 ) { + int old_good = rc80211_calc_net_goodness ( ctx, dev->rate ); + if ( old_good != best_net_good ) + DBGC ( ctx, "802.11 RC %p switching from goodness " + "%d to %d\n", ctx, old_good, best_net_good ); + + ctx->started = 1; + return best_rate; + } + + return dev->rate; +} + +/** + * Set 802.11 device rate + * + * @v dev 802.11 device + * @v rate_idx Index of rate to switch to + * + * This is a thin wrapper around net80211_set_rate_idx to insert a + * debugging message where appropriate. + */ +static inline void rc80211_set_rate ( struct net80211_device *dev, + int rate_idx ) +{ + DBGC ( dev->rctl, "802.11 RC %p changing rate %d->%d Mbps\n", dev->rctl, + dev->rates[dev->rate] / 10, dev->rates[rate_idx] / 10 ); + + net80211_set_rate_idx ( dev, rate_idx ); +} + +/** + * Check rate-control state and change rate if necessary + * + * @v dev 802.11 device + */ +static void rc80211_maybe_set_new ( struct net80211_device *dev ) +{ + struct rc80211_ctx *ctx = dev->rctl; + int net_good; + + net_good = rc80211_calc_net_goodness ( ctx, dev->rate ); + + if ( ! ctx->started ) { + rc80211_set_rate ( dev, rc80211_pick_best ( dev ) ); + return; + } + + if ( net_good < 0 ) /* insufficient data */ + return; + + if ( net_good > RC_GOODNESS_MAX && dev->rate + 1 < dev->nr_rates ) { + int higher = rc80211_calc_net_goodness ( ctx, dev->rate + 1 ); + if ( higher > net_good || higher < 0 ) + rc80211_set_rate ( dev, dev->rate + 1 ); + else + rc80211_set_rate ( dev, rc80211_pick_best ( dev ) ); + } + + if ( net_good < RC_GOODNESS_MIN ) { + rc80211_set_rate ( dev, rc80211_pick_best ( dev ) ); + } +} + +/** + * Update rate-control state + * + * @v dev 802.11 device + * @v direction One of the direction constants TX or RX + * @v rate_idx Index of rate at which packet was sent or received + * @v retries Number of times packet was retried before success + * @v failed If nonzero, the packet failed to get through + */ +static void rc80211_update ( struct net80211_device *dev, int direction, + int rate_idx, int retries, int failed ) +{ + struct rc80211_ctx *ctx = dev->rctl; + u32 goodness = ctx->goodness[direction][rate_idx]; + + if ( ctx->count[direction][rate_idx] < 16 ) + ctx->count[direction][rate_idx]++; + + goodness <<= 2; + if ( failed ) + goodness |= RC_PKT_FAILED; + else if ( retries > 1 ) + goodness |= RC_PKT_RETRIED_MULTI; + else if ( retries ) + goodness |= RC_PKT_RETRIED_ONCE; + else + goodness |= RC_PKT_OK; + + ctx->goodness[direction][rate_idx] = goodness; + + ctx->packets++; + + rc80211_maybe_set_new ( dev ); +} + +/** + * Update rate-control state for transmitted packet + * + * @v dev 802.11 device + * @v retries Number of times packet was transmitted before success + * @v rc Return status code for transmission + */ +void rc80211_update_tx ( struct net80211_device *dev, int retries, int rc ) +{ + struct rc80211_ctx *ctx = dev->rctl; + + if ( ! ctx->started ) + return; + + rc80211_update ( dev, TX, dev->rate, retries, rc ); + + /* Check if the last RC_TX_EMERG_FAIL packets have all failed */ + if ( ! ( ctx->goodness[TX][dev->rate] & + ( ( 1 << ( 2 * RC_TX_EMERG_FAIL ) ) - 1 ) ) ) { + if ( dev->rate == 0 ) + DBGC ( dev->rctl, "802.11 RC %p saw %d consecutive " + "failed TX, but cannot lower rate any further\n", + dev->rctl, RC_TX_EMERG_FAIL ); + else { + DBGC ( dev->rctl, "802.11 RC %p lowering rate (%d->%d " + "Mbps) due to %d consecutive TX failures\n", + dev->rctl, dev->rates[dev->rate] / 10, + dev->rates[dev->rate - 1] / 10, + RC_TX_EMERG_FAIL ); + + rc80211_set_rate ( dev, dev->rate - 1 ); + } + } +} + +/** + * Update rate-control state for received packet + * + * @v dev 802.11 device + * @v retry Whether the received packet had been retransmitted + * @v rate Rate at which packet was received, in 100 kbps units + */ +void rc80211_update_rx ( struct net80211_device *dev, int retry, u16 rate ) +{ + int ridx; + + for ( ridx = 0; ridx < dev->nr_rates && dev->rates[ridx] != rate; + ridx++ ) + ; + if ( ridx >= dev->nr_rates ) + return; /* couldn't find the rate */ + + rc80211_update ( dev, RX, ridx, retry, 0 ); +} + +/** + * Free rate-control context + * + * @v ctx Rate-control context + */ +void rc80211_free ( struct rc80211_ctx *ctx ) +{ + free ( ctx ); +} |