Note of Linux bottom-half handling - Softirq, tasklet, workqueue, and threaded interrupt

最近因為手上的問題，花了些時間了解 Linux 上的 bottom-half 機制，記錄下看了甚麼。

重點整理

Softirq

• Software Interrupt context
• Enable handling of hardware interrupt
• The timing of executing softirq handlers
• (1) exit of HW ISR
• (2) running at ksoftirqd
• (3) explicitly call do_softirq
• Not allowed bottom-half context switch
• no sleep, no scheduling, and no user memory access
• Normal priority kernel thread per CPU basis, i.e. ksoftirqd
• ksoftirqd/n, n is the CPU number
• Each softirq thread has the same softirq handler.
• Softirq of the same type can run on multiple CPUs
• Each CPU has a set of softirq pending status bits
• The registered softirq handlers are shared by CPUs
• When one softirq handler is running, another softirq handler can run on another CPU.
• Disable local CPU bottom-half
• Enable local CPU interrupt
• Statically allocated. Only 10 softirqs by default. 
• Has problem on loadable kernel module. Solved by using tasklet.
• Postpone the user-space execution
• softirq has time limit to prevent it's too long
• Basis of tasklet

Tasklet

• Implemented upon softirqs (tasklet_sofirq and hi_softirq)
• Software Interrupt context
• A tasklet only run on one CPU
• Different tasklets can run concurrently on multiple CPUs
• Per-cpu taskelet list
• Tasket_softirq and hi_softirq
• Run atomically in a run-to-complete fashion

Work queue

• Implemented upon kernel thread
• Process context
• Permit handlers to sleep

Above methods (softirq, tasklet, work queue) need us to explicitly arrange them in top-half handlers.

Threaded interrupts

• Recommended way to implement bottom-half
• Handle the complex of hardirq -> tasklet/softirq interaction and locking problems
• Prioritizing the handlers share an interrupt line

參考資料

...繼續閱讀

https://www.linkedin.com/pulse/kernel-software-interrupts-ram-gupta

第一篇我能看的懂的，白話講解 bottom-half 的機制

https://elinux.org/images/e/ef/InterruptThreads-Slides_Anderson.pdf

講解 threaded interrupt 的由來

https://hackmd.io/@sysprog/linux-interrupt

jserv 的上課筆記

https://ithelp.ithome.com.tw/articles/10253342

有比較 threaded interrupt 與其他方式的實驗

https://0xax.gitbooks.io/linux-insides/content/Interrupts/linux-interrupts-9.html

Trace Linux source 裡對 softirqs, tasklet, workqueue 的實作。可以深度的瞭解這三個的實作，只是長度有點長，需要時間理解。

https://www.oreilly.com/library/view/understanding-the-linux/0596005652/ch04s07.html

很仔細的講解 softirq, tasklet, 和 workqueue 的行為。用條列的方式解釋，可以搭配上面那篇的程式碼一起對照著看。有重點講解了 ksoftirq 的設計想法。

https://www.kernel.org/doc/htmldocs/kernel-hacking/basics-softirqs.html

短短的，直接把 softirq 應該記住的重點直接點出來

https://linux-kernel-labs.github.io/refs/heads/master/lectures/interrupts-slides.html#22

linux kernel interrupt document。用 lecture 的方式閱讀也蠻清楚的。

https://www.plantation-productions.com/Webster/www.artofasm.com/DOS/pdf/ch17.pdf

裡面有講到 exception, trap, 和 interrupt 這三個在這篇文章中的定義，拿來參考用。

" 

Trap: user requested to transfer control to a special subroutine

Exception: automatically generated trap of exceptional condition

Interrupt: external hardware event

"

https://zhuanlan.zhihu.com/p/88883239

講解 preempt_count 的實作，中文有附圖，很清楚。另外也有 softirq 的文章，一樣也是有圖也清楚。

https://stackoverflow.com/questions/26458730/ksoftirqds-bottom-halves-in-interrupt-or-process-context

解釋為什麼 softirq 跑在 kernel thread 中，卻還是屬於 interrupt context。

" 

ksoftirqd is implemented as a set of threads, each of which is constrained to only run on a specific CPU. They are scheduled (at a very high priority) by the normal task scheduler. This implementation has the advantage that the time spent executing the bottom halves is accounted to a system task. It is thus possible for the user to see that the machine is overloaded with interrupt processing, and maybe take remedial action.

Although the work is now being done in process context rather than bottom half context, ksoftirqd sets up an environment identical to that found in bottom half context. Specifically, it executes the softirq handlers with local interrupts enabled and bottom halves disabled locally. Code which runs as a bottom half does not need to change for ksoftirqd to run it. 

"

https://lwn.net/Articles/520076/

這篇有簡述 Softirq 的行為，還有提到 softirq 在 kernel 2.6.23 之後會跑在 normal user-level priority，舊一點的資料都是說 softirq 會跑在 highest priority。

在自己手上的 kernel 5.10 上驗證這點。

localhost ~ # ps -e -o uid,pid,ppid,pri,ni,cmd | grep ksoft

    0    13     2  19   0 [ksoftirqd/0]

    0    22     2  19   0 [ksoftirqd/1]

    0    28     2  19   0 [ksoftirqd/2]

    0    34     2  19   0 [ksoftirqd/3]

    0    40     2  19   0 [ksoftirqd/4]

    0    47     2  19   0 [ksoftirqd/5]

    0    53     2  19   0 [ksoftirqd/6]

    0    59     2  19   0 [ksoftirqd/7]

19 is normal user-level priority on kernel 5.10.

Cross compile mtd-utils

為什麼 GPIO input 要用 pull-up/pull-down，output 要用 push-pull 或 open-drain?

最近花了點時間研究了 GPIO 為什麼有那麼多的設定要選，有 pull-up / pull-down，還有 push-pull。上網一查，發現相關的心得文章超多，代表了有很多的人都跟我一樣，時間和精神去了解，然後覺得有點價值，值得寫文章記錄下來。

目前看了幾篇文章覺得很有參考價值的有下面幾篇。

Open Drain Output vs. Push-Pull Output

https://open4tech.com/open-drain-output-vs-push-pull-output/

...繼續閱讀

單片機IO口科普：推輓輸出、開漏輸出詳解

https://kknews.cc/tech/a4xx6.html

Demystifying Microcontroller GPIO Settings

https://embeddedartistry.com/blog/2018/6/4/demystifying-microcontroller-gpio-settings

電路常見問題小記之IO口漏電(leakage)

https://kknews.cc/code/bk94z89.html

我自己的理解是這樣的。

GPIO 從名稱就能知道，最重要的功能就是用來和外界做 Input 和 Output。從軟體的角度看，就像是 Chip 出了一個 pin 腳，外界只要接上那根 pin 就能跟 Chip 溝通了。

在軟體人的想像中，我想只要有線路接到 register 就夠了吧 ! 在想的仔細一點，加上軟體操作用的 register 好了。

可惜事情不是這麼簡單，現實的物理之壁很快就讓人認清現實。這麼做會有幾個問題要解決。這些問題是看著 GPIO 的設計後做的猜測，可能是為了解決這些問題才這麼做的。

1. Input 的波型不是方波的話，怎麼辦 ?
2. GPIO Pin 腳狀態是 floating 
3. output  如何提供足夠的電流輸出到外面的設備 ? 

Input 的波型不是方波的話，怎麼辦 ?

用 schmitt trigger  來解。

GPIO Pin 腳狀態是 floating 

GPIO 有三種狀態，High impedance，High (voltage)，Low (voltage)。

High 代表 digital 1, Low 代表 digital 0。根據 chip 的設計，通常 3.3V = High，0V = Low 。

'High impedance' 也可以寫成 'Hi-Z'，代表不上不下，這時的 GPIO pin 可能為 1 也可能為 0，看當下的使用環境而定。這個用途是，當跟其他設備共用一條線時，不影響正在輸出 High / Low 的設備。當沒有共用時，就需要給他一個確定的狀態，避免誤動作。為什麼 floating 會造成誤動作，詳細請看下面的連結，講得很清楚。

浮接 Floating 是甚麼? 電路的不確定因素

https://www.strongpilab.com/input-high-z-floating/

回到 GPIO，這個問題就用 pull-up/pull-down 來處理。pull-up 表示預設為 high，pull-down 表示預設為 Low。對應的外部設備動作，pull-up 隱含設備有動作時會拉 Low，pull-down 隱含設備動作時會拉 high。

output  如何提供足夠的電流輸出到外面的設備 ?

這個問題是我想像出來的，目前還沒找到使用 push-pull 的原因，看到的都是在講說 push-pull 的原理，但沒有講是用來解決甚麼問題。

目前看到的 GPIO 有兩種設計來提供電流給外部設備用，一種是 Chip 內的電流，一種是外部的電流。兩種都由 GPIO 來控制供給的時間點。

使用 Chip 內電流的方式稱為 push-pull。外部電流稱為 open-drain (或 open-collector)。

Push-pull

我這邊會加個 inverter 是因為，光只有 PMOS 和 NMOS 的組合，得到的會是一個 inverter。這跟我想要的，GPIO output 1 時輸出電流，output 0 時輸入電流的預期不合，所以才在把他反過來。可以看這一篇 https://en.wikipedia.org/wiki/Inverter_(logic_gate) 提到的 inverter 作法。

Open-drain

Open-drain 由外部提供電流，所以一定要接一個外面的電源。接法就像是 pull-up。

最後，有些 Chip 很聰明，可以讓使用者選擇要用 push-pull 或是 open-drain，有些就不行。這邊我想了一下，覺得可以加一個 NAND 來做，不過出來的結果不是很理想，不太懂怎麼做比較對。

下面的連結可以看我模擬的結果

http://www.falstad.com/circuit/circuitjs.html?cct=$+1+0.000005+10.20027730826997+50+5+43%0Af+288+160+368+160+33+1.5+0.02%0Af+272+240+368+240+32+1.5+0.02%0Aw+368+176+368+224+0%0Aw+368+144+368+64+0%0Aw+16+176+16+64+0%0Aw+368+256+368+320+0%0Aw+16+240+16+320+0%0Aw+368+336+368+320+0%0Aw+368+176+464+176+0%0Ar+464+176+464+256+0+100%0Ag+464+256+464+288+0%0AR+16+64+16+48+0+0+40+5+0+0+0.5%0Ag+16+320+16+352+0%0Ar+16+176+16+240+0+1000%0As+16+176+160+176+0+0+false%0Ag+368+336+368+352+0%0AR+368+64+368+32+0+0+40+5+0+0+0.5%0AR+592+176+592+64+0+0+40+12+0+0+0.5%0Ar+592+176+496+176+0+200%0Aw+496+176+464+176+0%0AI+208+240+272+240+0+0.5+5%0As+64+96+128+96+0+0+false%0A151+208+160+288+160+0+2+0+5%0Aw+160+176+208+176+0%0Aw+64+96+16+176+0%0Aw+208+240+160+176+0%0Aw+160+144+208+144+0%0Aw+128+96+160+144+0%0Ax+49+56+260+59+4+14+0%5Cs(off):open%5Csdrain,%5Cs1%5Cs(on):push-pull%0Ax+36+239+182+242+4+14+GPIO%5Csout:%5Cs0%5Cs(off),%5Cs1%5Cs(on)%0Ax+492+265+523+268+4+14+Load%0Ab+432+192+504+242+0%0Ab+53+149+125+215+0%0Ab+58+69+130+119+0%0Ao+9+64+0+4099+5+0.05+0+2+9+3%0A

Make produces "No such file or directory" error in Cygwin

最近需要裝 Cygwin 來 build code，當裝完後執行 Make 時卻發生找不到 source，一直說 "No such file or directory"。

奇怪的是，source 放在 Make 旁邊時可以找到，但是放在子資料夾或是不同資料夾的話就找不到。本來以為是自己路徑給錯，但仔細檢查後又是對的，用 cat 或 ls 也可以找到相對應的 source。

問了下 Google，就在這篇找到 Hint，用 'whereis make' 看了下 make 的路徑，才發覺用到了別的 toolchain 的 make，而不是 Cygwin 提供的 make。

https://unix.stackexchange.com/questions/131419/gcc-produces-erroneous-no-such-file-or-directory-under-cygwin/131425

...繼續閱讀

問題的原因就是我之前裝的 toolchain 裡也有提供 make 的 exe，我也有把這個 toolchain 加進 windows 的 PATH 中，結果我在 Cygwin 中做 make 時就誤用了這個 toolchain 的 make ，我應該使用的是 Cygwin installer 中提供的 make 才對。

我就把這個 toolchain 從 windows PATH 中移除後重開 Cygwin，再用一次 'whereis make' 確定 make 的路徑是 '/usr/bin/make.exe' 。重新 build code 時就沒有問題了。

context switch 到底在做甚麼?

簡單的說，'context switch' 就是切換  'context'。而所謂的 'context'，指的就是當下 CPU  registers 的內容。

因為當程式在執行時，所做的事情就是從 memory 中讀取指令和依照指令做計算。CPU 在做這兩件事情時，就是用 core registers (CPU 內部的 register) 來紀錄讀取到哪裡了，以及當作計算時的暫存區域。

當 CPU 做事做到一半，如果有事件發生了，而且這個事件的處理所用到的 core registers 會把目前的進度蓋掉的話，CPU 就會先需要把 core registers 目前的值先暫存到 memory 的某個地方，等 CPU 處理完事件之後，再把暫存的值讀回來，就可以從事件發生時中斷的地方在繼續處理。這就是所謂的 'context switch'。

...繼續閱讀

因為 CPU 的設計都不太一樣，要知道有哪些 core registers 需要存起來，就要去看 CPU 廠商提供的文件。一般來說可能要保存 Program Counter (PC)，stack pointer (SP)，和一些計算時會用到的 registers。

以 ARM CM4 來說的話，當發生 exception 時，CM4 需要儲存下圖中的 core registers。R0~R3, R12, LR, PC, xPSR。這邊沒有儲存 SP，原因不明，不過有需要的話，也可以自己存起來。對 CM4 來說，因為 IRQ 也屬於一種 exception，所以 IRQ 觸發後，也會自動先儲存這些  core registers 到 stack 中。

from: Cortex-M4 Devices Generic User Guide, p40

需要 context switch 的時候

目前我知道會需要做 'context switch' 的場景有三種，發生 Exception，發生 IRQ，和 OS scheduling。

Exception and IRQ Context Switch

CM4 有幾種不同的 exception type，IRQ 就被歸類為其中一種。因為 Exception 和 IRQ 被視為是相同的場景，所以處理的手法也一樣。

from: Cortex-M4 Devices Generic User Guide, p22

處理的手法有個名稱 'Exception Entry'，在 CM4 上很貼心的會在 exception 發生時自動地把一些 registers 存到 stack 中，這樣 programmer 就不用自己處理 exception 的 context switch 了。

from: Cortex-M4 Devices Generic User Guide, p39

至於 CM4 為什麼不是存全部的 registers 呢? 這就需要知道 caller register 和 callee register 的分別了。不同的 CPU 對這兩者的定義會不一樣，通常 CPU 會提供一份通稱 'ABI' 的文件來描述自家的 CPU 是如何使用 CPU register 的。

下圖就是 ARM ABI 對 core register 的定義。

from: Procedure Call Standard for the Arm Architecture, 6.1.1

文件中有一段重要的文字，間接說明了為什麼。

from: Procedure Call Standard for the Arm Architecture, 6.1.1

這段文字說明了，因為每個 subroutine (也就是進入一個 function 後)，在 function 中 compiler 會在使用到這些 register 前就自動先保存起來 (push 進 stack)，當 function 結束 return 後，原本的 caller 是不會察覺到這些 register 有被動過，也就是 'preserve the content'。

因為在 IRQ 的處理 function 中，也會有相同的行為，所以不用再特地去保存這些 register。不過需要注意的是，一定要是 C function 才有 compiler 的幫忙，若是 assembly 的話，就需要自己處理了。

OS scheduling Context Switch

接下來要說明的是由 OS scheduling 觸發的 context switch。這邊會以 FreeRTOS 當標的，因為我不懂 Linux...。

RTOS scheduler 排程的對象是 task，對每個 task 來說，CPU 就像是由自己獨享的資源，各個 task 之前不會預期有分享 CPU 這種假設。於是當 RTOS 在做 task context switch 時，所做的事情就是儲存所有的 core registers，跟前面提到的 exception 和 IRQ 不一樣的地方在這邊沒有在考慮 caller 和 callee register。

FreeRTOS context switch

直接看 FreeRTOS 的 code 如何處理 task context switch 就可以了，邏輯很好懂。

再換 task 之前，先把所有的 core registers 存到 task stack 中，再把目前 task 的 stack pointer 和 task control block (TCB) 也存進 task stack 裡，之後在選出下一個 task，選好後把 sp 換成新選好的 task 的 stack，在按照相反的順序把 task stack，TCB，以及 core registers 從 task stack 中拿出來用就完成了 task context switch。

以小寫字母標示的儲存內容，讀取順序以大寫字母表示。

	mrs r0, psp /* (a) load stack point(sp) to r0 */
	isb
	ldr r3, pxCurrentTCBConst /* Get the location of the current TCB. */
	ldr r2, [r3] /* Get 1st member of pxCurrentTCBConst */
	tst r14, #0x10 /* Is the task using the FPU context? If so, push high vfp registers. */
	it eq
	vstmdbeq r0!, {s16-s31} /* (b) Push FPU context */
	stmdb r0!, {r4-r11, r14} /* (c) Push the core registers. */
	str r0, [r2] /* (d) Push the new top of stack into the first member of the TCB. */
	stmdb sp!, {r0, r3} /* (e) push sp and pxCurrentTCBConst to stack head */
	mov r0, %0
	msr basepri, r0 /* clear IRQ base priority */
	dsb
	isb
	bl vTaskSwitchContext /* pick next task */
	mov r0, #0
	msr basepri, r0
	ldmia sp!, {r0, r3} /* (E) pop sp and pxCurrentTCBConst from stack head */
	ldr r1, [r3] /* (D) The first item in pxCurrentTCB is the task top of stack. */
	ldr r0, [r1]
	ldmia r0!, {r4-r11, r14} /* (C) Pop the core registers. */
	tst r14, #0x10 /* Is the task using the FPU context? If so, pop the high vfp registers too. */
	it eq
	vldmiaeq r0!, {s16-s31} /* (B) Pop FPU context */
	msr psp, r0 /* (A) change sp to task's stack */
	isb

view raw c hosted with ❤ by GitHub

From: FreeRTOS port on CM4F

參考資料

用 Google 找到的，跟 context switch 相關的內容。

How FreeRTOS Works
https://freertos.org/implementation/a00006.html
https://freertos.org/implementation/a00020.html

Definition of context switch for Linux
http://www.linfo.org/context_switch.html

FreeRTOS程式碼分析 -- 1
http://albert-oma.blogspot.com/2012/05/freertos-1.html

淺讀CuRT：task, context switch與scheduling
http://reborn2266.blogspot.com/2013/10/curttask-context-switchscheduling.html

Transform hex to decimal in excel

col\row   | 0    | 1   |
------------------------
       A  | 0x123| 291 |

...繼續閱讀

From 0x123 to 291

step 1. remove "0x" : =RIGHT(A0, LEN(A0)-2)
step 2. use "HEXTODEC" : =HEXTODEC(RIGHT(A0, LEN(A0)-2))

From 291 to 0x123

step 1. use "DECTOHEX" : =DECTOHEX(A1)
step 2. add prefix "0x": =CONCATENATE("0x", DECTOHEX(A1))