file_operations unlocked_ioctl

用 unlocked_ioctl() 取代 ioctl()

呼叫 ioctl() 會先用 lock_kernel() 來 lock，而呼叫 unlocked_ioctl() 沒有 lock ，unlocked_ioctl() 需自行確保有無問題，例如用 per-driver 或 per-device 的 mutexes 取代。unlocked_ioctl() 不再提供inode參數，但可以透過 filp->f_dentry->d_inode 取得。

lock_kernel()/unlock_kernel() 是 Big Kernel Lock (BKL)，在 Linux v2.6.39 deprecated。

參考

1. The new way of ioctl()

#if HAVE_UNLOCKED_IOCTL
#include <linux/mutex.h>
#else
#include <linux/smp_lock.h>
#endif

.
.
.

#if HAVE_UNLOCKED_IOCTL
mutex_lock(&fs_mutex);
#else
lock_kernel();
#endif

http://stackoverflow.com/questions/5956145/can-someone-help-me-replace-lock-kernel-on-a-block-device-driver

• compat_ioctl() 是 32-bit process 在 64-bit 系統呼叫 ioctl() 用，和 unlocked_ioctl() 一樣沒有 BKL。
• https://kernelnewbies.org/BigKernelLock：BKL 最終在 Linux v2.6.39 移除。Big Kernel Lock (BKL) 是想要 get rid of 的 old serialization method，用更 fine-grained locking 取代，如 mutex、spinlock 和 RCU。BKL 是 recursive lock，意思是可以從已經持有的 thread 取得。聽起來方便，但容易 introduces all sorts of bugs。另一個問題是，當 thread sleep，BKL 自動釋出。這避免 mutex 在有些情況 lock order 問題，但也 creates more problems because it makes it really hard to track what code is executed under the lock。

lock-free

術語比較：

• lock-free：沒鎖死。以系統觀點，只要執行夠長的時間，至少會有一個執行緒有進展。
• lockless (lock-freedom?)：不用鎖。不用 lock 共用資料。不用鎖 (lockless) 未必不會鎖死 (lock-free)，也可能鎖死。
• wait-freedom?：不用等
• obstruction-freedom
• non-blocking (非阻塞)：
• 任何 thread 的失敗或暫停不會造成其它 thread 的失敗或暫停。non-blocking 演算法如果能保證 system-wide progress 是 lock-free，如果能進一步保證 per-thread progress 是 wait-free。
• 在電信網路，是指建立新的連線路徑不用調整現有的連線。沒缺陷的電話交換機總是可以建立連線 (nonblocking minimal spanning switch)。

參考

1. https://hackmd.io/@sysprog/concurrency-lockfree
2. https://hackmd.io/@sysprog/concurrency-atomics

lock contention

微處理器專用 atomic 指令及軟硬體設計考量：ABA 問題, memory ordering 及 memory barrier、多核處理器特性、C11 標準的 <stdatomic.h>、Linux 核心介面

SPSC (single-producer and single-consumer)

SPMC (single-producer, multiple-consumer)

Linux File I/O

問題

• read()、write()、ioctl() 有 race 問題嗎？

參考

TLPI §4 & §5

4 FILE I/O: THE UNIVERSAL I/O MODEL
4.1 Overview
4.2 Universality of I/O
4.3 Opening a File: open()
4.3.1 The open() flags Argument
4.3.2 Errors from open()
4.3.3 The creat() System Call
4.4 Reading from a File: read()
4.5 Writing to a File: write()
4.6 Closing a File: close()
4.7 Changing the File Offset: lseek()
4.8 Operations Outside the Universal I/O Model: ioctl()
4.9 Summary
4.10 Exercises

5 FILE I/O: FURTHER DETAILS
5.1 Atomicity and Race Conditions
5.2 File Control Operations: fcntl()
5.3 Open File Status Flags
5.4 Relationship Between File Descriptors and Open Files
5.5 Duplicating File Descriptors
5.6 File I/O at a Specified Offset: pread() and pwrite()
5.7 Scatter-Gather I/O: readv() and writev()
5.8 Truncating a File: truncate() and ftruncate()
5.9 Nonblocking I/O
5.10 I/O on Large Files
5.11 The /dev/fd Directory
5.12 Creating Temporary Files
5.13 Summary
5.14 Exercises

Saturation arithmetic

static inline uint32_t saturated_addu32(uint32_t x, uint32_t y)
{
        uint32_t sum = x + y;
        sum |= -(sum < x);
        return sum;
}

非負整數相加，結果變小時 OR -1，否則 OR 0，不用判斷式。

static inline uint32_t saturated_subu32(uint32_t x, uint32_t y)
{
        uint32_t z = x - y;
        z &= -(z <= x);
        return z;
}

非負整數相減，結果變大時 AND 0 成為 0，否則 AND -1 不變，不用判斷式。

https://en.wikipedia.org/wiki/Saturation_arithmetic

Rounding integer division

Rounding integer division (instead of truncating)

static inline uint32_t rounding_divu32(uint32_t x, uint32_t y)
{
        return (x+(y>>1))/y;
}

先加上除數的一半再除。

AM335x ADC

AM335x 有 8-channel ADC，可支援 4/5/8-線電阻式觸控。

• 8 類比輸入 AN0~AN7 (≤1.8V)，VDDA_ADC (1.8V)，VSSA_ADC (GND)，VREFN，VREFP
• ADC 是 12-Bit 的 Successive Approximation Register (SAR) ADC
• ADC 時脈最快 24MHz。
• 每個 ADC 轉換至少需要 15 ADC 時脈，包括 1x Sample Delay (SOC)、1x 取樣、12x Digitize、和 1x EOC。
• 取樣率？200K Samples per Second (24M = 15 x 8 x 200K ？)
• 輸入選自 8 類比輸入的多工。
• 整體運作是由一些 sequencer 達成，包括平常沒事在 idle，和 16 個 ADC 步驟、佮一個 touchscreen 充電步驟。
• 每個步驟 (包括 idle) 可設定個別 AFE 訊號，包括 single-ended 或 differential、RFM/INP/INM/RFP 選擇、WPN/YPN/XNP/YNN/YPP/XNN/XPP 狀態。
• 每個 ADC 步驟和充電步驟各自可以設定是否啟動，和 Open Delay。
  
• 每個 ADC 步驟可轉換一個 channel，可設定 Sample Delay、是否範圍檢查、使用 FIFO 0 或 FIFO 1、是否 Average 1/2/4/8/16、SW 或 HW、和 One-shot 或 Continuous。
  
• Programmable FSM sequencer。
• Software register bit for start of conversion
• Optional start of conversion HW synchronized to Pen touch or external HW event (but not both)
• Single conversion (one-shot) 或 Continuous conversions
• Sequence through all input channels based on a mask
• Programmable OpenDelay before sampling each channel
• Programmable sampling delay for each channel
• Programmable averaging of input samples - 16/8/4/2/1
• Differential or singled ended mode setting for each channel
• Store data in either of two FIFO groups
• Option to encode channel number with data
• Support for servicing FIFOs via DMA or CPU
• Programmable DMA Request event (for each FIFO)
• Dynamically enable or disable channel inputs during operation
• Stop bit to end conversion
• Support for the following interrupts and status, with masking:
• Interrupt for HW pen (touch) event
• Interrupt for HW Pen Up event
• Interrupt after a sequence of conversions (all non-masked channels)
• Interrupt for FIFO threshold levels
• Interrupt if sampled data is out of a programmable range
• Interrupt for FIFO overflow and underflow conditions
• Status bit to indicate if ADC is busy converting

參考

1. AM335x Sitara™ Processors datasheet
2. AM335x and AMIC110 Sitara™ Processors Technical Reference Manual

• https://www.teachmemicro.com/beaglebone-black-adc/
• http://beaglebone.cameon.net/home/reading-the-analog-inputs-adc
• https://beagleboard.org/static/librobotcontrol/group___a_d_c.html：Robotics Cape 和 BeagleBone Blue 包含兩個 voltage divider 量測 2-cell lithium battery 和 9-18V DC power jack 電壓，分別用 c_adc_batt() 和 rc_adc_dc_jack() 讀取。Robotics Cape 還有 6-pin JST-SH 插座可連結 4 potentiometers 或類比訊號到 AIN。

Successive-approximation ADC

Successive Approximation Register (SAR) ADC 是一種 ADC 作法，結果採二進位搜尋，多次 DAC 回溯比較，逐步縮小範圍確認：

1. 值先清為 0，並把輸入取樣後維持住，方便後續多次比較。
2. 最高位元預設為 1，經過 DAC 相當於和 1/2 的位置，如果比較小就清為 0。
3. 再來次高位元先設為 1，相當於和 1/2 ± 1/4 的位置比較，如果比較小就清為 0。
4. 再來 1/2 ± 1/4 ± 1/8 位置，... 愈來愈接近。
5. 如果要輸出 12-bit 的值，總共需要經過 12 次比較後輸出。

優點是省電，缺點是較慢。