Building Linux Kernel Modules Faster: Internal and external

*For Newbie Linux Kernel and Device Driver developers*.

Most repetitive activity for Kernel and Device Driver developers. is building modules they work on and installing them. So lets discuss few tricks to build them faster way.

Traditionally, when we change a source code of a module, we need to 

a) Build the entire kernel again
make; make module;make modules_install;make install
(optionally using "-jN" option to make)
b) reboot and use the new modules.

But we can avoid reboot by 

a) Build the entire kernel again
b) Remove the old module 
c) Insert the new module.

Building the kernel itself is a time consuming process, especially when we just want to update code specific to our module. So for that we make use linux kernel's support and procedures for building external modules  i.e., modules which are not present in the kernel tree for modules in the kernel tree. Sounds Confusing?

Lets say we have written a new module and wanted to compile it, then we write a makefile which invokes the kernel makefile with below option:

make modules M=<Dir_of_new_Module>

But to compile a internal module (module which is present in the kernel tree) we use the same trick, except the makefile is already present. Just follow the below procedure

Procedure: 

1. make silentoldconfig  (Optional)
• whenever Kconfig is changed., For other cases like make and make modules (without M=) this is run by kernel makefile itself.
2. make modules M=<path_to_dir>
3. make modules_install M=<path_to_dir>
4. Remove the old module and Re-Insert the new one.

Still interested of know-how, see the steps in detail:

Details:

1) Whenever we change Kconfig, .config will be updated and we need to tell the kernel makefile to use the new .config instead of using old one.This does that.

2) This uses the makefile in the module sub directory and compiles the files w.r.t #1 .config options.

3) This will install the compiled modules in to the install path /lib/modules//`uname -r`/kernel/ (or) /lib/module/`uname -r`/extra/ depending on whether the module is internal/external. In our case its always extra as we are using "M=" option for building modules. We can add some prefix (extra folder name under the above paths).

Also it used the depmod utility (through a wrapper shell script: scripts/depmod.sh) to generate the below files which will later be used by modprobe.

• /lib/modules/`uname -r`/modules.alias
• /lib/modules/`uname -r`/modules.alias.bin
• /lib/modules/`uname -r`/modules.builtin
• /lib/modules/`uname -r`/modules.builtin.bin
• /lib/modules/`uname -r`/modules.ccwmap
• /lib/modules/`uname -r`/modules.dep
• /lib/modules/`uname -r`/modules.dep.bin
• /lib/modules/`uname -r`/modules.devname
• /lib/modules/`uname -r`/modules.ieee1394map
• /lib/modules/`uname -r`/modules.inputmap
• /lib/modules/`uname -r`/modules.isapnpmap
• /lib/modules/`uname -r`/modules.ofmap
• /lib/modules/`uname -r`/modules.order
• /lib/modules/`uname -r`/modules.pcimap
• /lib/modules/`uname -r`/modules.seriomap
• /lib/modules/`uname -r`/modules.softdep
• /lib/modules/`uname -r`/modules.symbols
• /lib/modules/`uname -r`/modules.symbols.bin
• /lib/modules/`uname -r`/modules.usbmap

Lets discuss the important ones below: 

• /lib/modules/`uname -r`/modules.dep
• Depmod is a utility which will use the "System.map" and try to work out the dependencies between the modules and create a file called "modules.dep", used by modprobe to insert (insmod) the modules in proper order.
• /lib/modules/`uname -r`/modules.order and /lib/modules/`uname -r`/modules.symbols will be used in that process.
• /lib/modules/`uname -r`/modules.alias
• It identifies the HW devices each device driver supports and writes to a file "module.alias" using which the linux kernel device model can insert the driver along with its dependencies (using modprobe and modules.dep) when it  enumerates a new HW device using PCI/USB ..
• /lib/modules/`uname -r`/modules.builtin
• This gives a list of modules which are staically linked to the kernel forming part of vmlinuz.
• /lib/modules/`uname -r`/modules.<BUS>map
• These files will the known drivers for devices and give informtion regarding the device like vendorid, subsystemid, deviceclass etc.
• This is used to create module.alias

4) Now that we have all the necessary files, use below commands "-v" is for verbose and "-r" is for using rmmod. By default it used insmod.

•     modprobe -v -r 
•     modprobe -v 

Installing depmod and modprobe: Install the "https://www.kernel.org/pub/linux/utils/kernel/module-init-tools/" package with your distro specific instructions.

Common Caveats:

1) If you are not seeing the changes in the new module: 

Probably you are re-inserting the old modules add "-v" to the modprobe and check the timestamps in the path from where modprobe is insmod-ing the module and your module in the kernel tree.  

Running "make modules_install" again should do, if all else fails then try copying manually.

2) If you are seeing a warning about module version check, while inserting the module: 

Probably you are using the above procedure for two dependent modules, like changing a function in cfg80211 and using that one in mac80211. 

Its better to use a directory which hold the directory of both of these, in the above case use "make modules  modules_install M=net/". For more details read Module Versioning Section in R#3.

References:

1) Linux kernel Makefile :-) 

2) Building External Modules

3) Kernel Docs: Building Linux kernel

802.11 AC Primer: Whats all the fuzz about?

802.11ac is the upcoming big standard with tremendous increase in the data rates and throughput if properly utilized. Lets take a Brief/Raw look at the all the new features and how they help to achieve greater data rates and spectrum utilization.

PHY Features

• 256 QAM

• Very high order modulation scheme which increases the spectral efficiency only when used with beamforming technology, as high order modulation schemes are susceptible to noise and interference.

• Compared to 11n 64QAM, spectrum efficiency improves by 33% 

• Require about 30dB increase in SNR and coverage area is reduced (beam forming can solve this)

• Sub-carriers
• The maximum subcarriers that can be used with OFDM in WLAN is 64/20MHz, as of now 11ac uses this limit most efficiently, the next standard will run out the this limit, its time to increase it to 128/20MHz #IEEE :-)
• 11a/11g ==> 52
• 11n        ==> 57
• 11ac      ==> ~59
• 80 MHz

• 160MHz

• 80+80 MHz

• Single continuous 160MHz and 2 discrete 80MHz can also be combined as 160MHz channel, increases the throuhgput but not the spctral efficiency.

• 8 Spatial Streams

• Sounds high, yeah for a single user it doesn't make sense, but with Multi User MIMO we can exploit this to increase the overall spectrum efficiency.

• MU-MIMO

• Instead of using all the Antennae for a single user (Even though some of them are not really used for some MCSes) we can use each antenna for a single user (max up to 4) and serve all of them in parallel.  This poses few issues like how do we identify each STA? What about group frames? How can a STA for which the data is not destined can ignore the frames? 

• The answer to these questions is the additional features introduced in MAC as explained below. 

• AES-256

• GMAC and GCMP

• Present in 11n in most of the enterprise AP's, now its official along with few other extra algorithms.

MAC Features

PHY ID's (Included in the VHT SIG field) 

Basic motivation is determine if the packet is not destined for you at the earliest possible stage (PHY instead of MAC) and go to micro sleep. (Most likely the case when MU-MIMO is in use)

GroupID

"An AP determines the possible combinations of STAs that can be addressed by an MU PPDU by assigning
STAs to groups and to specific user positions within those groups. (through a new GroupID management Frame).
So after decoding the TXVECTOR the STA can decided whether the frame is for itself (or) not."

Note: Group ID 0 is reserved for transmissions to AP and Group ID 63 is reserved for downlink SU transmissions

Partial AID: The partial AID is a non-unique identifier of a STA and is 9 bits conveyed in the TXVECTOR To identify whther the transmissions are destined to a STA/not, used in conjunction with GroupID.

PHY Power-saving with PHY ID's

TXOP Sharing 

In the TXOP won for a particular AC, we can also send frames destined for others AC's to other STA's as well.

"This mode only applies to an AP that supports DL-MU-MIMO. 

The AC associated with the EDCAF that gains an EDCA TXOP becomes the primary AC. TXOP sharing is allowed when primary AC traffic is transmitted in a VHT MU PPDU and resources permit traffic from secondary ACs to be included, targeting up to four STAs."

TXOP power save

Sounds weird but is a good feature. Basically in a TXOP for MU-MIMO, if the frame is not destined for the STA it can doze off for that TXOP duration.

"If the AP allows non-AP VHT STAs to enter Doze state during a TXOP, then a non-AP VHT STA that is in VHT TXOP power save mode may enter the Doze state till the end of that TXOP when one of the following

conditions is met:

— On receipt of a VHT MU PPDU, the STA determines that it is not a member of the group indicated by the RXVECTOR parameter GROUP_ID. 

— On receipt of an SU PPDU, the STA determines that the RXVECTOR parameter PARTIAL_AID is neither equal to 0 nor does it match the STA’s partial AID. 

— The STA finds that the PARTIAL_AID in the RXVECTOR matches its partial AID but the RA in the MAC header of the corresponding frame that is received correctly does not match the MAC address of the STA."

 References:

1. IEEE Discussions: Spectrum Efficiency 
2. IEEE Discussion: PHY Powersave
3. 802.11ac-draft 5.0

An Introduction to Wireless Sniffing and Dissection

Lets try to understand and learn how sniffing wireless networks work and how to configure it in different platforms like Windows and Linux.

Our primary concentration will be Omnipeek and Wireshark the 2 most used Packet Capture and Analysis Tools predominant in wireless LAN industry.

1. Sniffing Wireless in Windows
2. Sniffing Wireless in Linux
3. Sniffing through Multiple Interfaces
4. Monitor Vs. Promiscuous Mode (Coming Soon)
5. Automate Sniffing Process (Coming Soon)

OFDM in WLAN: 802.11n: Similar to 802.11a and 802.11g with minor changes

In the previous article we have discussed about OFDM in 802.11 a/g, now let's take a look at how OFDM works in 11n. 

OFDM has little to do with the drastic 11n rate boost, MIMO is the key player there. Lets leave the MIMO part aside, its a candidate for next article. As far as OFDM is concerned it will work per antenna, but the basic concept per antenna is the same as 11g with few changes.

20 MHz:  This is same as 802.11 a/g but 

a) With an extra 4 sub carriers.

In 802.11a/g we use 48 sub-carriers for data and 4 sub-carriers for pilot. But in 11n we make use of an extra 4 sub-carriers from the reserved for data sub-carriers.So this results in increased throughput.

b) Short Guard Interval (Optional)

we have short guard interval introduced in 11nIn the previous article we have take the guard interval as 1/4 of symbol time, now in 11n they have still decreased the guard interval to 1/8 of the symbol time. So it comes down to,                          3.2us *1/8=0.4us 

Lets take an example to understand:

a) Full Guard Interval

20MHz/64=0.3125; 1/0.3125 =3.2us + 1/4 * 3.2 us=4 us

b) Short guard Interval

20MHz/64=0.3125; 1/0.3125 =3.2us + 1/8 * 3.2 us=3.6 us

Note: Important point to note here is that while doing the calculations for the FFT period we have considered the maximum carriers 64 not the used carriers, so the above calculation of 3.2us holds good in spite of increased sub carriers.

40 MHz: 

Its same as 20MHz but the process repeated in both primary and secondary channels.

So as derived above the total no of sub-carriers in  a 40MHz channel is 52*2 (primary and secondary) + 4 (extra).

The reason for these extra 4 data sub carriers is that we don't need that many (8) pilot sub-carriers combined for both the channels, so we converted some of them to data sub carriers.

Data Sub-Carriers = 52 *2 = 104

Pilot sub-carriers  = 4 + 4  = 8

======================

Total Sub-carriers = 112 with 8 pilot sub-carriers.

Now out of that if remove 2 sub-carriers from 8 and convert them to 2 and add 2 more (why?) 

======================

Data Sub-carriers = 104+2 (from pilot)+2 (extra)=108

Pilot sub-carriers = 4-1 + 4-1=6

======================

Total sub-carriers = 108+6 =114

I am not sure of the exact rationale behind adding some number of sub carriers  but its safe to attribute that to the evolution, as the IEEE std progresses they are trying to make use of all the reserved sub-carriers in that process.

With the same logic in the previous article we can similarly derive the rate calculations for the above 20MHz and 40Mhz as well. The above tables from the IEEE 802.11-2012 will help you.

What is OFDM?: Simplified..

Lets take a look at the technology that literally commanding all and any form of wireless communications OFDM without requiring any prior electronics knowledge.

Orthogonal Frequency Division Multiplexing is the most sought modulation technique in today's cutting edge wireless either it be 802.11 (WLAN), 802.16(WiMax), 3GPP 36 series (LTE)..

Single Carrier Modulation:

In the traditional communications we make use of a single Tx antenna and a single Rx Antenna. All the incoming data is modulated using a single carrier and sent OTA, at the Rx side its is  demodulated and data after removing the carrier is given out.

Multi-Carrier Modulation:

FDM: 

But in order to gain high throughput a new scheme is introduced. Where in we divide the channel in to different sub channels and assign a carrier to each sub-channel for modulation known as sub-carrier and finally multiplex all the carriers+data and send using the single Tx Antenna.
But in order to avoid interference (inter-symbol interference) we use a guard spacing between the sub channels causing in bandwidth wastage.

OFDM: 

In order to save the wastage and use it effectively we choose the sub-channels and sub-carriers such that they are orthogonal to each other meaning they don't interfere with each other. So we can skip the guard spacing between the sub-channels and save bandwidth.

FDM Vs. OFDM

Truly speaking it should be termed as FDMO, as you will see why just in a moment. lets understand each word in detail in the acronym.

Frequency Division (FD):

Instead of modulating all data with one carrier, divide the bandwidth in to equally separated sub-channels and assign a carrier to each sub-channel called sub-carrier.

Multiplexing (M):

As we have multiple sub-carriers but a single Tx antenna we need to map all the sub-carriers rather we need to multiplex all of them and send OTA. We make use Parallel to Serial converter for this.

Orthogonality(O):

We all know from the high school maths that orthogonality means "product of slopes = -1" meaning one signal will not overlap with the other.

In a similar context in the time domain a sub channel is represents as a rectangle which in a frequency domain converts to a "sinc" wave, now if we multiplex the "sinc" waves of all sub carriers sub channels it will look something like the below.

Now at the Rx side we can decode this wave because of the orthogonality, see the "arrows" they represent the frequency at which impact of all other sub carriers is zero, so we get to Rx only that particular sub-carrier we are interested in.

*2: By using an IFFT for modulation we implicitly chose the spacing of the subcarriers in such a way that at the frequency where we evaluate the received signal (indicated as arrows) all other signals are zero.

Advantages:

1. Saves bandwidth
2. Carries more no of data than a conventional carrier.

Disadvantages:

1. Highly depends on the orthogonality achieved, need a good sync on Tx and Rx and also no multipath effect.
2. High PAPR: Peak to Average Power Ratio.

The reason for high PAPR is that, as we use many sub-carriers with same bandwidth, the sum of peak power of all the sub-carriers varies instantaneously.
OFDM exhibits peaks whose power strongly exceeds the mean  power: the signal is said to have a high PAPR. This prevents use of high-efficiency amplification devices (High Power Amplifiers, HPA), which can cause nonlinearities reuslting in in-band distortion and increases Out-Of-Band  Radiation (OOBR), inter Symbol Interference and a high Bit-Error-Rate (BER).

Mitigations

1. 

a) Pilot: Instead of using all the sub-carriers/channels for data, use some selected sub carriers to send with zero-data so that the Rx can tune itself with the Tx. These are kind of training subcarriers.

b)  Cyclic Prefix (CP): In order to overcome the MultiPath effect, OFDM implements a clever technique of CP where in we first need to find the "Doppler Spread" of the multipath channel and then copy that amount of time from the data signal from the last to the first. So that even if that signal undergoes the multipath fading, we still have the data intact only the copied part is lost.

Doppler Spread: The amount of delay induced by the multipath channel to the 1st signal causing to overlap with the 2nd singal leading to infamous inter symbol interference. 

2.  There are many methods but below are famous ones

• Clipping and Filtering

• Peak Windowing

References:

1. History behind OFDM
2. Orthogonality in OFDM

3. Why High PAR 

4. PAPR Reduction Techniques

Note: All the pictures here are taken from the references and some additional resources. The author do not claim any copy right.

Wireless LAN and Linux Together

With the advent of opensource the development time has come down hugely and the quality has improved quickly. For all those involved with WLAN/Wi-Fi and Opensource lets take a look at the wlan architecture in linux based on opensource mac80211 framework.

Block diagram explaining linux WLAN architecture. Please see below for details.

User-Space:

Configuration: wpa_supplicant and hostapd:

All the applications which interact directly with the user lie here. They can a GUI/CLI based ones for eg. network manager in ubuntu/fedora distributions are UI based ones, but the core part are the CLI based ones eg. wpa_supplicant for controlling the STA part of it and hostapd for controlling the AP part.

Both are configuration file based along with their cli versions (wpa_cli, hostapd_cli) to send commands on the fly.

They support different features like SME, MLME, Security, Wifi-Direct (P2P),  AP and STA configurations.

Tools:

We also have tools to send commands to the driver directly to set some parameters such as channel, bandwidth, some custom commands etc.

The Bridge: User and Kernel

Now how the various applications in userspace communicate to the core entities in the kernel? Well, we have different approaches but all are based on different socket interfaces.

1. WExt ==> Generic Wireless Extensions: IOCTL Interface
2. NL80211==> Netlink Sockets
3. HostAP,==> Raw Packet Sockets
4. Chipset specific:

•               Atheros==> IOCTL Interface 
•               Prism,IPW etc.

Kernel Space

Configuration and UMAC

For opensource world the framework in kernel for WLAN is mac80211, it separates itself in to 2 kernel modules

• cfg80211.ko: Which handles all the configuration, user space interaction
• mac80211.ko: Protocol: Upper MAC , driver interaction.

Most of the features and management is handled by the mac80211 module with the help of lower MAC.

Lower MAC Drivers

Lowe MAC drivers act as a bridge between the UMAC and the chipset (Firmware and HW). They do all the device initialization, registration with OS, Bug Registration, Interrupts registration etc through the services provided by the linux kernel.

A well written driver follows these conventions

• Maintains a OS Independent Layer: Easy portability to different OSes.
• Maintains a UMAC Independent Layer: Easpy portability to different UMAC's: Proprietary, opensource, 3rd party etc.
• Bus Abstraction Layer: Maintains compatibility across different Physical Buses like PCI, PCIe, AHB, SDIO etc.

Chipset: Firmware and HW

The full 802.11 protocol functionality is implemented here.

The firmware which probably runs on a separate processor/micro-controller configures and controls the hardware and also interacts with the host(The driver) through a messaging interface specific to the chipset (control path)

The Data path generally involves a DMA controller in the HW which takes care of generating interrupts to the host processor and transferring packets to and from the Host to the HW queues.

References:

1. wpa_supplicant_hostapd_devel_doc
2. For details on these click userspace_configurations.
3. wpa_supplicant