2022q1 vwifi

contributed by < rickywu0421 >

sysprog21/vwifi

• 2022q1 vwifi
  • PR #27 - Implement real AP and STA mode
    • 1. STA 得以 scan 真實的 Host AP 網路介面
    • 2. STA 得以 connect 真實的 Host AP 網路介面
    • 3. 實作 AP 轉送封包機制
  • PR #24 - Refactor and assign one wiphy to each interface
    • 引進虛擬網路介面
    • 使實驗環境可以支援超過兩個以上的網路介面
  • PR #23: Implement cfg80211_ops->get_station
    • 透過 3rd order sine approximation 模擬 RSSI
  • 參考資料
  • 開發者文件

PR #27 - Implement real AP and STA mode

• commit: 97f03a

vwifi 於本次 commit 實現 HostAP 以及 STA modem, 在此之前 STA 的通訊方式類似 adhoc。

新的實驗環境如下圖：

實作上主要完成了下列部分：

1. STA 得以 scan 真實的 Host AP 網路介面
2. STA 得以 connect 真實的 Host AP 網路介面
3. 實作 AP 轉送封包機制, 禁止 BSS 內的 STA 進行 Ad-hoc like 通訊

1. STA 得以 scan 真實的 Host AP 網路介面

以下展示部分實作：

static void inform_bss(struct owl_vif *vif)
{
    struct owl_vif *ap;

    list_for_each_entry (ap, &owl->ap_list, ap_list) {
        ...
        bss = cfg80211_inform_bss_data(
            vif->wdev.wiphy, &data, CFG80211_BSS_FTYPE_UNKNOWN, ap->bssid, tsf,
            WLAN_CAPABILITY_ESS, 100, ie, ap->ssid_len + 2, GFP_KERNEL);
        ...
    }
}

其作法很單純, 即是走訪整個 AP list owl->ap_list, 並將 AP 的部分資訊透過呼叫 cfg80211_inform_bss_data() 通知核心。

2. STA 得以 connect 真實的 Host AP 網路介面

以下展示部分實作：

static void owl_connect_routine(struct work_struct *w)
{
    struct owl_vif *vif = container_of(w, struct owl_vif, ws_connect);
    struct owl_vif *ap = NULL;
    
    /* Finding the AP by request SSID */
    list_for_each_entry (ap, &owl->ap_list, ap_list) {
        if (!memcmp(ap->ssid, vif->req_ssid, ap->ssid_len)) {
            cfg80211_connect_result(vif->ndev, NULL, NULL, 0, NULL, 0,
                                    WLAN_STATUS_SUCCESS, GFP_KERNEL);
            ...
            vif->sme_state = SME_CONNECTED;
            vif->ap = ap;
            ...
            /* Add STA to bss_list, and the head is AP */
            list_add_tail(&vif->bss_list, &ap->bss_list);
            ...
        }
    }
    ...
}

這個部分也很單純, 走訪整個 AP list owl->ap_list, 比對使用者傳入的 vif->req_ssid 以及 ap->ssid 是否一致, 若是, 則呼叫 cfg80211_connect_result() 通知核心此 STA 連接到了該 BSS。

最後更新 STA 的狀態, 並把 STA 加入到該 AP 的 BSS list。

3. 實作 AP 轉送封包機制

過往 vwifi 在傳送封包上是以 Ad-hoc 的形式傳送, 即封包傳送沒有 AP 介入。現在實作了真實世界的 STA 以及 Host AP mode, 故不再允許此通訊方式。取而代之的是 AP 負責 relay STA 間的封包, 具體處理方式依據網路介面為 STA 或 AP, 以及 TX/RX 有所不同：

• STA TX: 不論是 unicast/multicast/broadcast 封包, 一律傳到已經關聯 (associated) 的 AP
• STA RX: 不論是 unicast/multicast/broadcast 封包, 均把封包交給核心網路子系統。
• AP TX:
  • unicast: 根據封包的目的 MAC 地址, 將封包發送到對應的網路介面
  • broadcast/multicast: 將封包送往 BSS list 中的所有 STA, 除了發送者之網路介面 (don't send back)
• AP RX:
  • unicast: 查看封包的目的 MAC 地址確認是否是給自己的, 若是, 則把封包交給核心網路子系統, 若否, 則傳送封包到對應 STA 的網路介面, 並且不要將封包交給核心網路子系統
  • broadcast/multicast: 將封包送往 BSS list 中的所有 STA, 除了發送者之網路介面 (don't send back), 並且將封包交給核心網路子系統

這邊展示 AP RX 的部份程式碼：

static void owl_rx(struct net_device *dev)
{
    struct sk_buff *skb, *skb1 = NULL;
    ...
    struct ethhdr *eth_hdr = (struct ethhdr *) skb->data;

    /* Receiving a multicast/broadcast packet, send it to every
     * STA except the source STA, and pass it to protocol stack.
     */   
    if (is_multicast_ether_addr(eth_hdr->h_dest)) {
        pr_info("owl: is_multicast_ether_addr\n");
        skb1 = skb_copy(skb, GFP_KERNEL);
    }
    /* Receiving a unicast packet */
    else {
        /* The packet is not for AP itself, send it to destination
         * STA, and do not pass it to procotol stack.
         */
        if (!ether_addr_equal(eth_hdr->h_dest, vif->ndev->dev_addr)) {
            skb1 = skb;
            skb = NULL;
        }
    }

    if (skb1) {
        pr_info("owl: AP %s relay:\n", vif->ndev->name);
        owl_ndo_start_xmit(skb1, vif->ndev);
    }

    /* Nothing to pass to protocol stack */
    if (!skb)
        return;
    
    /* Pass the skb to protocol stack */
    skb->dev = dev;
    skb->protocol = eth_type_trans(skb, dev);
    skb->ip_summed = CHECKSUM_UNNECESSARY; /* don't check it */
    netif_rx_ni(skb);
}

這邊要先介紹兩個區域變數: skb 以及 skb1:

• skb: 指向要被送至核心網路子系統的 socket buffer
• skb1: 指向要被傳送至其他 STA 之 socket buffer

這邊列個 AP RX 的表格幫助大家記憶：

packet type	skb	skb1
unicast (給自己)	exist	NULL
unicast (給其他人)	NULL	exist
multicast/broadcast	exist	exist

繼續看下去, is_multicast_ether_addr() 在封包是 multicast/broadcast 時回傳 1 (該函式判斷 MAC 地址中的第一個 byte 的 LSB 是否為 1, 由於 broadcast 之所有 bit 皆為 1, 故會使函式回傳 1)。若回傳 1, 則表示封包要被傳送至其他 STA, 並且要被送至核心網路子系統, 故 skb 與 skb1 都指向 socket buffer。這邊是關鍵, 由於 vwifi TX 完成後會把 socket buffer free 掉 (這是驅動程式 TX 的工作), 若 skb 與 skb1 指向同個 socket buffer, 此時可能導致核心網路子系統讀到該被 free 掉的區段, 而使核心崩潰。故我用 skb_copy() 將 skb 完整複製一份給 skb1 (有興趣的讀者可以去看看 skb_clone, pskb_copy() 以及 skb_copy() 的差別)。

若封包是 unicast, 則判斷封包是否是給自己的, 若是, 則將封包送至核心網路子系統, 若否, 則傳送封包到指定的網路介面, 並且不要將其送至核心網路子系統。

PR #24 - Refactor and assign one wiphy to each interface

• commit: bfc9330

此 commit 的目的是為了讓程式能彈性的支援之後將被實作的各種模式 (hostap/station/IBSS mode)。

引進虛擬網路介面

原本的程式將 "網路介面相關" 與 "獨立於網路介面" 的成員分散在兩個不同的結構體, 在參考 Atheros ath6kl 以及 Broadcom FullMAC 後, 引進虛擬網路介面, 其作為 struct net_device 以及 cfg80211 的擴充, 表示一個虛擬網路介面：

struct owl_vif {
    struct wireless_dev wdev;
    struct net_device *ndev;
    struct net_device_stats stats;

    /* Currently connected BSS id */
    u8 bssid[ETH_ALEN];
    u8 ssid[IEEE80211_MAX_SSID_LEN];
    /* For the case the STA is going to roam to another BSS */
    u8 req_bssid[ETH_ALEN];
    u8 req_ssid[IEEE80211_MAX_SSID_LEN];
    struct cfg80211_scan_request *scan_request;
    enum sme_state sme_state;  /* connection information */
    unsigned long conn_time;   /* last connection time to a AP (in jiffies) */
    unsigned long active_time; /* last tx/rx time (in jiffies) */
    u16 disconnect_reason_code;

    struct mutex lock;
    struct timer_list scan_timeout;
    struct work_struct ws_connect, ws_disconnect;
    struct work_struct ws_scan, ws_scan_timeout;
    struct list_head rx_queue; /* Head of received packet queue */

    /* List entry for maintaining multiple private data of net_device in
     * owl_context.vif_list.
     */
    struct list_head list;
};

使實驗環境可以支援超過兩個以上的網路介面

原本的程式將一個 wiphy 共享給所有的網路介面, 在原本的測試情境下這樣做沒有問題：

首先我先解釋這個實驗環境：

1. 為何需要 network namespace：假設我們將 owl0 的 IP address 設為 10.0.0.1, owl0sink 的 IP address 設為 10.0.0.2, 接著透過下 ping 10.0.0.2, 預期結果是封包會透過 owl0 傳送而 owl0sink 接收, 然而真正的行為是封包會通過 lo0 (loopback) 傳送及接收, 因為核心通過路由表發現 10.0.0.1 以及 10.0.0.2 在同一個主機上。Network namespace 實現了網路虛擬化, 其可以從主機中隔離出網路介面以及路由表, 而這使我們的實驗得以進行。
2. 為何需要 macvlan：這是上述的延伸, 無線網路環境下加入 network namespace 是以 wiphy 為單位的, 也就是說, 兩個虛擬網路介面 (owl0 與 owl0sink) 不能被加入不同的 network namespace, 因為他們共用同一個 wiphy (然而 Ethernet 沒有這項限制)。因此我們在兩個虛擬網路介面之上建立 macvlan, 其能將封包傳至下層裝置並能被加入 network namespace。

這樣的實驗環境存在一個問題：只容許兩個虛擬網路裝置互相溝通, 因為傳送封包的程式實作如下：

/* @dev: interface structure for current device.
 * @dest_np: interface structure for destination device.
 */
dest_np =
        list_last_entry(&owl->netintf_list, struct owl_ndev_priv_context, list);
if (dest_np->ndev == dev)
    dest_np = list_first_entry(&owl->netintf_list,
                               struct owl_ndev_priv_context, list);

其作法很簡單, 確認是否 dest_np == dev, 若是則賦值 dev 為 list 中的另一個節點。

為了 vwifi 的擴充性, 這段程式改寫為：

/* @dest_vif is similar to original @dest_np */
if (is_broadcast_ether_addr(eth_hdr->h_dest)) {
    list_for_each_entry (dest_vif, &owl->vif_list, list) {
        if (dest_vif == vif)
            continue;
        ...
    }
}
/* The packet is unicasting */
else {
    list_for_each_entry (dest_vif, &owl->vif_list, list) {
        if (ether_addr_equal(eth_hdr->h_dest, dest_vif->ndev->dev_addr)) {
            ...
        }
    }
}

首先先判斷封包是否為廣播封包 (如 ARP request, dhcp request 等等), 若是則傳送給所有網路介面, 若否則迭代網路介面, 確認封包的目的 MAC 位址是否與網路介面的地址相同, 僅相同時傳送封包。

這迎來了一個問題：實驗環境真正傳送封包的是 macvlan 裝置, 也就是封包的目的 MAC 位址是其中一個 macvlan 裝置的 MAC 位址而不是 owl0 或 owl0sink 的 MAC 位址, 於是檢查封包目的 MAC 位址的方式會失敗。

於是為了解決問題, 我們又生出了一個問題：我們必須移除 macvlan 裝置, 將 owl0 及 owl0sink 加入到各自的 network namespace。但上述有解釋過為何需要 macvlan, 就是因為 owl 以及 owl0sink 共用同一個 wiphy, 因此這兩個介面勢必會在同一個 network namespace 中。

解決問題: 賦予每個虛擬網路介面不同的 wiphy, 使每個虛擬網路介面可以被加入到不同的 network namespace。

新的實驗環境：

PR #23: Implement cfg80211_ops->get_station

• commit: 2af271d

實作 cfg80211_ops->get_station 使得某個 station 可以透過 nl80211 獲得同個 BSS 中的其他 station 的資訊, 包括：

• TX 資訊
• RX 資訊
• 時間相關資訊
• 無線接收訊號強度 (RSSI)

其中原本模擬 RSSI 的作法是在範圍內生成隨機的值, 但這使得訊號強度不規則跳動, Jserv 老師希望我可以使訊號強度平滑化且不隨機跳動。

透過 3rd order sine approximation 模擬 RSSI

$sin(x)$ 的值位於

$-1$ 到

$1$ 之間, 且函數不存在不可微分的點, 因此很適合用來做為平滑化的函數。

泰勒級數

我們將

$sin(x)$ 透過泰勒級數在

$x=0$ 的位置展開到第三項：

$$\begin{array}{rl}f(x)& =sin(x)\\ & =sin(0)+\frac{si{n}^{(1)}(0)}{1!}x+\frac{si{n}^{(2)}(0)}{2!}{x}^2+\frac{si{n}^{(3)}(0)}{3!}{x}^3\\ & =x-\frac{1}{6}{x}^3\end{array}$$

由於

$sin(x)$ 是奇函數, 故最後只會留下奇次項。我們將

$f(x)$ 對

$x$ 作圖,

$x$ 範圍為

$[0,1/2\pi ]$：

我們可以發現,

$f(x)$ 在

$x$ 尚未接近

$\frac{1}{2}\pi$ 前都很正常, 但在

$x\to \frac{1}{2}\pi$ 時開始轉向, 這使得

$f(\frac{1}{2}\pi )\ne 1$。這樣的結果是因為我們使用的是泰勒級數的近似, 但其實結果還可以接受, 只是需要做一些調整使函式在 crucial point (

$x=0$ or

$x=\frac{1}{2}\pi$) 能夠經過正確的點。

曲線擬合

我們透過三次多項式來重新近似

$sin(x)$, 由於

$sin(x)$ 是奇函數, 我們可以省略偶次項：

$$\{\begin{array}{l}{S}_3(x)=ax-b{x}^3=x(a-b{x}^2)\\ S_3^{{}^{\prime }}(x)=a-3b{x}^2\end{array}$$

我們的期望是

$S_3(x)$ 之值介於

$0$ ~

$1$ 之間, 故只需代入 cricial point 使得

$S_3(0)=0$ (不需代入, 因為

$S_3(0)$ 勢必為

$0$) 且

$S_3(\frac{1}{2}\pi )=1$：

$$\{\begin{array}{l}{S}_3(\frac{1}{2}\pi )=1=\frac{\pi }{2}a-(\frac{\pi }{2}{)}^{3}b\\ S_3^{{}^{\prime }}(\frac{1}{2}\pi )=0=a-3(\frac{\pi }{2}{)}^{2}b\end{array}$$

$$\Rightarrow \{\begin{array}{l}a=\frac{3}{\pi }\approx 0.955\\ b=\frac{4}{{\pi }^3}\approx 0.129\end{array}$$

於是最終的方程式如下：

$S_3(x)=\frac{3}{\pi }x-\frac{4}{{\pi }^3}{x}^3$

我們將其作圖,

$x$ 範圍為

$[0,\frac{1}{2}\pi ]$:

可以發現 crucial point 的值正常了。要注意的是, 參數

$a$,

$b$ 的值並非唯一, 若帶入不同的點則會有不同的結果, 也許這組參數的正確率不是最高的, 但他至少確保 crucial point 的值是對的。

座標轉換

若使用原本的單位 (radius),

$x$ 的 crucial point 將會是

$0,\frac{1}{2}\pi ,\pi ,\frac{3}{2}\pi ,2\pi ,...$, 這使得範圍不好界定。將

$x$ 經過座標轉換 (

$z=x/(\frac{1}{2}\pi )$) 後使得 crucial point 變成

$0,1,2,3,4,...$：

$$\begin{array}{rl}{S}_3(x)& =\frac{3}{\pi }x-\frac{4}{{\pi }^3}{x}^3\\ & =\frac{3}{2}\frac{2x}{\pi }-\frac{1}{2}(\frac{2x}{\pi }{)}^3\\ & =\frac{3}{2}z-\frac{1}{2}{z}^3\\ S_3(z)& =\frac{1}{2}z(3-z^2)\end{array}$$

實作第一步：floating-point to fixed-point

上述的方程式是基於 floating-point 的,

$z$ 以及

$S_3(z)$ 都要以浮點數表式, 這顯然是不符合預期的, 我們可以將輸入以及輸出拉伸到更大的值 (震盪頻率降低), 並用 fixed-point 表示。

為了將 floating-point 的函數轉換成 fixed-point 函數, 我們需要加上幾個 factor:

• scale of outcome:
  $2^A$,
  $[-1,1]\Rightarrow [-2^A,2^A]$
• scale of angle:
  $2^n$, 這相當於將
  $\frac{1}{2}\pi$ 擴展到
  $2^n$, 也就是
  $z=x/2^n$。
  $x$ 從
  $0$ 走到
  $2^n$ 相當於走完一個 sine quardrant (
  $\frac{1}{4}$ 個週期)。
• scale inside the parentheses:
  $2^p$, 這是為了防止運算時發生 overflow。

採用到原函數：

$$\begin{array}{rl}{S}_3(z)& =\frac{1}{2}z(3-z^2)2^A\\ & =z(3-z^2)2^{A-1}\\ & =x\cdot 2^{-n}(3-x^2\cdot 2^{-2n})2^{A-1}\\ & =x(3-x^2\cdot 2^{-2n})2^{A-1-n}\\ & =x(3\cdot 2^p-x^2\cdot 2^{p-2n})2^{A-1-n-p}\\ S_3(x)& =x(3\cdot 2^p-x^2/2^r)/2^s,\\ & wherer=2n-p,s=n+p+1+A\end{array}$$

經過測試, 以下是

$x$ 每若干個 ms 帶入 jiffies 時震盪頻率最理想的參數集合：

A	n	p	r	s
12	6	10	2	5

實作第二步：對稱性

我們的

$S_3(z)$ 近似的範圍僅限

$z=[-1,1]$ (雖然我們只有近似

$z=[0,1]$, 但由於 sine 函數是奇函數, 故

$z=[-1,0]$ 的值也會是對的), 但 sine 函數的 domain 是無限大的。於是我們要用對稱性讓同個週期內的剩下三個 sine quardrant 映射到左右第一個 sine quardrant。

見下圖：

以下 Q0 代表

$z=[0,1)$, Q1 代表

$z=[1,2)$, 以此類推。

我們可以發現 Q0 的值是正確的, 而 Q3 的值恰巧等於 Q(-1) 的值, 故有問題的是 Q1 及 Q2。不過我們發現, Q1 及 Q2 對

$z=1$ 鏡像後值就正常了, 我們可以根據以下方程式鏡像:

$$z=1-(z-1)=2-z$$

實作 3rd order sine approximation 程式碼

而程式要如何判斷現在是處於哪個 quardrant 呢？

我們回到 fixed-point 的參數

$n$, 若

$n=6$ 為, 則

$z=x/2^6$, 若我們要走完一個 sine 函數的週期, 即是

$z=[0,4)$, 則

$x=[0,2^8)$。因此, 我們可以透過從 LSB 往 MSB 方向的 bit 6 與 bit 7 組合判斷 (以 32 bit bitstream 為例)：

$$b=\stackrel{bit8\sim 31}{\overbrace{............}}\stackrel{bit0\sim 7}{\overbrace{\underset{Q}{\underbrace{01}}010001}}$$

只有 Q2 與 Q3 需要做鏡像, 而我們發現 (b >> 6) ^ (b >> 7) = 1 即代表 Q2 或 Q3, 反之則為 Q1 或 Q4。但這樣做還不夠, 我們要讓 bit 8 ~ bit 31 成為 bit 7 的 sign extension, 這樣才能確保整個 bit 8 ~ bit 31 不會影響結果。

具體作法是：把 b 左移 ((32 - 2) - n) = 24 個 bit：

x = x << (30 - n);

則原本的 bit 7 會跑到 MSB 得位置, 此時進行以下判斷:

if ((x ^ (x << 1)) < 0)
    x = (1 << 31) - x;

條件成立則表示 MSB (原本的 bit 7) 以及 MSB 的下一個 bit (原本的 bit 6) 不同時為 0 或 1, 即 Q2 或 Q3, 此時進行鏡像

$x=2-x$ (1 << 31 在此時表示 2 (記得 x 已經被左移過了), 也就是 0b10....)。

最後記得右移回去：

x = x >> (30 - n);

因為 x 是 signed integer, 故右移會自動進行 signed extension。

最後代入

$S_3(x)$:

return (x * ((3 << p) - ((x * x) >> r))) >> s;

完整程式碼如下：

static inline s32 __sin_s3(s32 x)
{
    /* S(x) = (x * (3 * 2^p - (x * x)/2^r)) / 2^s
     * @n: the angle scale
     * @A: the amplitude
     * @p: keep the multiplication from overflowing
     */
    const int32_t n = 6, A = 12, p = 10, r = 2 * n - p, s = n + p + 1 - A;

    x = x << (30 - n);

    if ((x ^ (x << 1)) < 0)
        x = (1 << 31) - x;

    x = x >> (30 - n);
    return (x * ((3 << p) - ((x * x) >> r))) >> s;
}

此函式的參數 x 可為任一 32 bit ineger, 而回傳值範圍為 -2^A ~ 2^A。

正規化回傳值

對回傳值進行操作, 使值介於 -100 ~ -30 (RSSI 合理的範圍為 -100 dBm ~ -30 dBm)。這邊要注意不能用 floating point 變數 (Linux 核心不使用 FPU)。

#define SIN_S3_MIN (-(1 << 12)) /* -2^A */
#define SIN_S3_MAX (1 << 12)    /* 2^A */
static inline s32 rand_int_smooth(s32 low, s32 up, s32 seed)：
{
    s32 result = __sin_s3(seed) - SIN_S3_MIN;
    result = (result * (up - low)) / (SIN_S3_MAX - SIN_S3_MIN);
    result += low;
    return result;
}

呼叫此函式：

s32 rssi = rand_int_smooth(-100, -30, jiffies);

cfg80211_ops->get_station() 之 RSSI 作圖

每若干 ms 透過 iw (netlink) 得到 cfg80211_ops->get_station() 之 RSSI, 記錄 1000 次, 並對其作圖：

可見 RSSI 具有穩定且平滑化的特性。

參考資料

• Braodcom FullMAC source code
• Atheros ath6kl source code
• Another fast fixed-point sine approximation

開發者文件

• Linux 802.11 Driver Developer’s Guide
• Linux Wi-Fi Driver Tutorial: How to Write a Simple Linux Wireless Driver Prototype
• mac80211_hwsim
• Emulating WLAN in Linux - part I: the 802.11 stack
• Emulating WLAN in Linux - part II: mac80211_hwsim
• virt_wifi