2026年1月20日 星期二
修復 v4l2loopback 0.15.0 的 V4L2 緩衝區佇列問題
## 問題現象
使用 GStreamer v4l2sink 將影像送到 v4l2loopback 虛擬攝影機時出現錯誤：
```
WARN v4l2bufferpool: buffer X was not queued, this indicates a driver bug
```
經過分析發現是 v4l2loopback 0.15.0 違反 V4L2 規格所致。
## V4L2 緩衝區佇列規格
V4L2 規格定義的緩衝區使用流程：
1. **VIDIOC_REQBUFS** - 配置緩衝區
2. **VIDIOC_QBUF** - 將緩衝區排入驅動程式佇列
3. **VIDIOC_DQBUF** - 從驅動程式佇列取出緩衝區
核心規則：DQBUF 只能回傳先前透過 QBUF 排入的緩衝區。
正確流程：`QBUF → (處理) → DQBUF → QBUF → (處理) → DQBUF ...`
v4l2loopback 0.15.0 的錯誤流程：`(預填充) → DQBUF → (自動循環) → DQBUF → (自動循環) → DQBUF ...`
錯誤點：完全不需要 QBUF，DQBUF 永遠有可用緩衝區。
## v4l2loopback 0.15.0 的問題
### prepare_buffer_queue() 預先填充佇列
```c
/* 原始碼 */
for (pos = 0; pos < count; ++pos) {
bufd = &dev->buffers[pos];
if (list_empty(&bufd->list_head))
list_add_tail(&bufd->list_head, &dev->outbufs_list);
}
```
問題：所有緩衝區在配置後立即被加入輸出佇列，沒有經過 QBUF。
### vidioc_dqbuf() 循環使用緩衝區
```c
/* 原始碼 */
bufd = list_first_entry_or_null(&dev->outbufs_list, ...);
if (bufd)
list_move_tail(&bufd->list_head, &dev->outbufs_list);
```
問題：使用 `list_move_tail()` 將緩衝區移到佇列尾端，形成循環。
### 違反規格的行為
1. 緩衝區未經 QBUF 就出現在輸出佇列
2. DQBUF 回傳從未排入的緩衝區
3. 緩衝區自動循環使用
實際流程：`DQBUF → DQBUF → DQBUF ...` (完全不需要 QBUF)
### GStreamer 的檢查
GStreamer v4l2bufferpool 會追蹤已排入的緩衝區。收到未排入的緩衝區時報錯：
```
WARN v4l2bufferpool: buffer X was not queued, this indicates a driver bug
```
這是正確的行為，因為驅動程式確實違反了規格。
## 修復方法
### 修改 prepare_buffer_queue()
清空輸出佇列，不要預先填充：
```c
/* 清空輸出佇列 */
list_for_each_entry_safe(bufd, n, &dev->outbufs_list, list_head) {
list_del_init(&bufd->list_head);
}
/* 重設緩衝區狀態 */
for (pos = 0; pos < count; ++pos) {
bufd = &dev->buffers[pos];
unset_flags(bufd->buffer.flags);
dev->bufpos2index[pos % count] = bufd->buffer.index;
}
```
### 修改 vidioc_dqbuf()
移除緩衝區，不要循環使用：
```c
bufd = list_first_entry_or_null(&dev->outbufs_list, ...);
if (bufd)
list_del_init(&bufd->list_head); /* 移除，不循環 */
```
### 修復後的行為
- 輸出佇列初始為空
- 緩衝區只在透過 QBUF 排入時才進入輸出佇列
- DQBUF 移除緩衝區，不循環使用
- 符合 V4L2 規格要求
## 測試驗證
修復前：
```bash
gst-launch-1.0 icamerasrc ! v4l2sink device=/dev/video0
# ERROR: buffer X was not queued, this indicates a driver bug
```
修復後：
```bash
gst-launch-1.0 icamerasrc ! v4l2sink device=/dev/video0
# 正常運作，無錯誤訊息
# Firefox/Chrome 可正常使用虛擬攝影機
```
## 技術細節
### 為什麼原設計會預先填充？
v4l2loopback 作為虛擬裝置，可能想簡化緩衝區管理，確保永遠有可用緩衝區。但這違反了 V4L2 規格，與嚴格遵循規格的程式（如 GStreamer）不相容。
### list_del_init vs list_move_tail
- `list_del_init()`: 明確表示「緩衝區不在佇列中」
- `list_move_tail()`: 暗示「移到另一個位置」，語義模糊
使用 `list_del_init()` 讓緩衝區狀態更清楚。
### 多執行緒考量
正確的緩衝區狀態追蹤在多執行緒環境下很重要，可避免競爭條件。
## 參考資料
- V4L2 Buffer: https://www.kernel.org/doc/html/latest/userspace-api/media/v4l/buffer.html
- VIDIOC_QBUF/DQBUF: https://www.kernel.org/doc/html/latest/userspace-api/media/v4l/vidioc-qbuf.html
- V4L2 Streaming I/O: https://www.kernel.org/doc/html/latest/userspace-api/media/v4l/io.html
- GStreamer v4l2bufferpool: https://gitlab.freedesktop.org/gstreamer/gstreamer/-/blob/main/subprojects/gst-plugins-good/sys/v4l2/gstv4l2bufferpool.c
## 上游貢獻
修補程式已提交至上游：https://github.com/v4l2loopback/v4l2loopback/pull/656
## 結論
V4L2 緩衝區管理規格的核心原則：
1. 明確的狀態轉換：QBUF → DQBUF
2. 應用程式控制：由應用程式決定何時提供緩衝區
3. 可預測行為：嚴格遵循規格
當應用程式報告 "driver bug" 時，通常確實是驅動程式的問題。
解析位元運算公式 n & ~(((n + 1) & ~n) >> 1)
# 前言
在解決「尋找最小的 $x$ 使得 $x \lor (x + 1) = n$ 」這個問題時，我們得出了一個結論：對於奇數 $n$ ，答案是將 $n$ 的二進位表示中，「末尾連續的 1」序列裡最高位的那一個 `1` 修改為 `0`。
例如：如果 $n$ 的二進位是 `...01111`，我們目標是把它變成 `...00111`。
這個操作可以透過以下這行精簡的位元運算公式完成：
```cpp
n & ~(((n + 1) & ~n) >> 1)
```
這篇筆記旨在拆解這個複合表達式，逐步說明其工作原理。
---
# 公式拆解
這個公式可以分為三個主要步驟來理解，我們由內而外進行分析。
我們的目標 $n$ 範例設為 **23**，二進位表示為 `00010111`。
我們的目標是將末尾三個 `1` 中最左邊的那個（值為 4 的位元）關閉。
## 步驟一：找出右邊數來第一個「0」的位置
**表達式核心：** `(n + 1) & ~n`
這是非常經典的位元操作技巧，用於定位最低位的 `0`。
1. **`n + 1` 的進位特性**：
當一個整數加 1 時，其二進位末尾所有的連續 `1` 都會因為進位而變成 `0`，直到遇到第一個 `0`，該位置會變成 `1`，進位停止。
* (23) = `00010111`
* (24) = `00011000` (注意末尾三個 1 變成了 0，它們左邊的 0 變成了 1)
2. **`~n` 取反**：
* `~n` = `11101000`
3. **`&` (AND) 運算**：
將上述兩個結果進行 AND 運算，只會保留同時為 `1` 的位元。
```
00011000 (n + 1)
& 11101000 (~n)
----------------
00001000 (結果為 8)
```
**小結**：這一步成功分離出了 從右側開始數第一個非 `1` 的位置。
## 步驟二：鎖定目標位元（向右移位）
**表達式：** `(步驟一的結果) >> 1`
我們在步驟一找到了第一個 `0` 的位置（在範例中是第 3 位，數值為 8）。
但我們的目標是修改這個 `0` 位置**右邊**的那一個 `1`（也就是末尾連續 `1` 序列的最高位）。
因此，我們將步驟一的結果向右移動一位：
* `00001000 >> 1` = `00000100` (數值為 4)
**小結**：這一步得到了一個「遮罩 (Mask)」，這個遮罩只有我們想要修改的那一個目標位元是 `1`，其他都是 `0`。
## 步驟三：清除目標位元
**表達式：** `n & ~(步驟二的遮罩)`
現在我們有了目標遮罩 `Mask = 00000100`。我們要利用這個遮罩把 對應位置的 `1` 變成 `0`，並保持其他位置不變。
這是標準的「清除位元」操作：
1. **`~Mask` (遮罩取反)**：
製造一個工具，目標位置為 `0`，其他位置全為 `1`。
* `~Mask` = `11111011`
2. **`n & (~Mask)`**：
將原始的 與這個反向遮罩做 AND。
* 目標位置：`1 & 0` 結果為 `0`（成功清除）。
* 其他位置：`x & 1` 結果仍為 `x`（保持不變）。
```
00010111 (n, 即 23)
& 11111011 (~Mask)
----------------
00010011 (結果為 19)
```
# 總結
回顧整個流程：
1. `00010111` (原始 n)
2. `00001000` (找到第一個 0)
3. `00000100` (右移，鎖定目標 1)
4. `11111011` (取反，準備清除工具)
5. `00010011` (與原數 AND，完成清除)
這個公式 `n & ~(((n + 1) & ~n) >> 1)` 利用了加法進位的特性和基本的邏輯閘操作，在不使用任何迴圈的情況下，精確地完成了「關閉末尾連續 1 中最高位」的任務。這是一種高效且常見於底層優化的寫法。
2026年1月17日 星期六
在 Copilot CLI 使用 Spec Kit 流程圖
我把使用的大概細節跟過程記錄在 https://hackmd.io/@fourdollars/SpecKit 上面，用 feat: Add shared storage support for multi-unit Concourse CI deployments #5 這個 Pull Request 來練習完整走過整個流程，總共產生了 122 commits 跟 43 個檔案變更，過程有苦有樂也有辛酸，感覺在帶一個做事很快不會抱怨也很主動積極的新同事，但是就是要處處盯著他做事，幫他解決一些卡住的地方。
Concourse CI Machine Charm 是我正在開發的一個使用 Juju 快速架構管理維護 Concourse CI 服務的一套解決方案，已經可以從 edge channel 拿來使用了，不過還在開發中還有許多地方沒有完善，所以還沒有穩定釋出版本。
2026年1月6日 星期二
深入解析 grep 的「Broken pipe」錯誤：隨機出現的原因與優雅解法
最近我在 [ChromeOS Flex](https://chromeos.google/products/chromeos-flex/) 的 Linux 環境中使用 [Homebrew](https://brew.sh/) 時，總是會隨機看到 `grep: write error: Broken pipe`。後來去檢查相關程式碼，發現是這行 `grep -E "^(flags|Features)" /proc/cpuinfo | grep -q "ssse3"` 指令造成的。
這個錯誤雖然不一定影響最終結果，但在特定環境下出現總是讓人感到困惑。為什麼這行看似普通的管線指令會隨機報錯？今天就來深入探討其成因，並提供修正方案。
## 「破裂的管線」錯誤成因
這個錯誤的核心，在於 Linux 作業系統處理**行程（Process）**與**管線（Pipe）**的機制。
當我們執行上述指令時，發生了以下連鎖反應：
1. **前端寫入（Producer）**：
第一個指令 `grep -E ...` 負責讀取 CPU 資訊，並持續將符合條件的資料寫入管線。
2. **後端讀取與提早退出（Consumer）**：
管線另一端的 `grep -q "ssse3"` 負責接收資料。關鍵在於 `-q` (quiet) 參數，它告訴 `grep` 一旦找到 "ssse3"，就**立即停止讀取並退出程式**。
3. **管線斷裂（Broken Pipe）**：
當後端 `grep` 退出後，管線的讀取端隨之關閉。然而，前端的 `grep` 此時可能還在嘗試寫入剩餘的資料。當它試圖寫入這條「已關閉」的管線時，系統便會發送 **SIGPIPE** 訊號，導致行程終止並印出 `write error: Broken pipe`。
## 為何錯誤是隨機出現的？
既然機制如此，為何不是「每次」都報錯？這歸因於**競爭條件（Race Condition）**。
電腦的排程器決定了兩個程式執行的快慢：
* **沒事發生的情況**：前端 `grep` 產出資料的速度夠快，或者資料量剛好夠小，在後端退出前就已經寫完並結束了。
* **報錯的情況**：後端 `grep -q` 很快就找到了 "ssse3" 並關閉管線，而前端還來不及寫完剩下的資料，導致寫入失敗。
這種執行時間上的微小差異，決定了你是否會看到這行錯誤訊息。
## 更優雅的解決方案
既然問題出在「多個指令透過管線傳輸」的時間差，最穩健的解法就是**避免使用管線**，將邏輯整合到單一 `grep` 指令中。
我們可以將原本的指令：
```bash
grep -E "^(flags|Features)" /proc/cpuinfo | grep -q "ssse3"
```
改寫為：
```bash
grep -qE '^(flags|Features).*\bssse3\b' /proc/cpuinfo
```
### 改寫後的優點：
* **消除競爭條件**：單一行程運作，完全根除「管線破裂」的可能性。
* **效能提升**：省去了啟動兩個行程與建立管線的開銷。
* **精準度提高**：
* `^(flags|Features)`：鎖定行首。
* `.*\bssse3\b`：利用 `\b`（單詞邊界）精確匹配 "ssse3"，避免誤判類似字串。
下次若在 Script 中發現類似的隨機管線錯誤，不妨檢查是否使用了會提早退出的指令（如 `grep -q`、`head` 等），並嘗試將其整合以提升穩定性！
順便生了一個 [pull request](https://github.com/Homebrew/brew/pull/21366) 給 Homebrew
2026年1月5日 星期一
自幹了一個 Agent Skills - Launchpad Skill
放在 https://github.com/fourdollars/lp-api/ 專案底下的 launchpad 目錄底下，當然就是用 lp-api 這個小工具來串接。
我自己有在 OpenCode, GitHub Copilot CLI, Gemini CLI 上面成功掛載起來使用。
基本上就是把 AI Agent 接上 Launchpad，用自然語言去叫 AI 做自己想要做的事情。
以下是幾張 OpenCode 上使用的示範。
有興趣的人可以去看看 Agent Skills 了解一下。
2025年11月28日 星期五
Kadane's algorithm
昨天練習的題目是 3381. Maximum Subarray Sum With Length Divisible by K，題目的最佳解是利用 Kadane's algorithm，我覺得比較容易理解的方式是先計算前面 k-1 個 kSum 之後，再往後面用 Kadane's algorithm 來解。
如果是寫 C++ 是這樣：
class Solution {
public:
long long maxSubarraySum(vector< int>& nums, int k) {
const int n = nums.size();
vector< long long> kSum(k, 0);
long long maxSum = numeric_limits< long long>::min(), prefixSum = 0;
for (int i = 0; i < k - 1; ++i) {
prefixSum += nums[i];
kSum[i] = prefixSum;
}
for (int i = k - 1; i < n; ++i) {
prefixSum += nums[i];
int r = i % k;
maxSum = max(maxSum, prefixSum - kSum[r]);
kSum[r] = min(kSum[r], prefixSum);
}
return maxSum;
}
};
寫 Python3 是這樣：
class Solution:
def maxSubarraySum(self, nums: List[int], k: int) -> int:
n = len(nums)
kSum = [0] * k
prefixSum = 0
maxSum = float("-inf")
for i in range(k - 1):
prefixSum += nums[i]
kSum[i] = prefixSum
for i in range(k - 1, n):
prefixSum += nums[i]
r = i % k
maxSum = max(maxSum, prefixSum - kSum[r])
kSum[r] = min(kSum[r], prefixSum)
return maxSum
寫 Go 是這樣，這邊要注意即便是使用 math.MinInt64 還是要用 int64() 明確轉型，不然預設會用 int 然後就會跟後面的 int64 衝突。
func maxSubarraySum(nums []int, k int) int64 {
n := len(nums)
kSum := make([]int64, k)
prefixSum, maxSum := int64(0), int64(math.MinInt64)
for i := range n {
prefixSum += int64(nums[i])
if i < k-1 {
kSum[i] = prefixSum
continue
}
r := i % k
maxSum = max(maxSum, prefixSum-kSum[r])
kSum[r] = min(kSum[r], prefixSum)
}
return maxSum
}
寫 Rust 是這樣，沒什麼特別要注意的地方，反正寫錯時編譯器會提醒你該如何修正。 :-P
impl Solution {
pub fn max_subarray_sum(nums: Vec< i32>, k: i32) -> i64 {
let k = k as usize;
let n = nums.len();
let mut kSum = vec![0i64; k];
let mut prefixSum = 0i64;
let mut maxSum = i64::MIN;
for i in 0..(k-1) {
prefixSum += nums[i] as i64;
kSum[i] = prefixSum;
}
for i in (k-1)..n {
prefixSum += nums[i] as i64;
let r = i % k;
maxSum = maxSum.max(prefixSum - kSum[r]);
kSum[r] = kSum[r].min(prefixSum);
}
maxSum
}
}
不曉得為何，寫 Rust 有最愉快的感覺。 :-P
2025年11月17日 星期一
Binary Search
今日練習的題目是 300. Longest Increasing Subsequence 主要是需要使用到 Binary Search
首先是 C++ 的 lower_bound
class Solution {
public:
int lengthOfLIS(vector< int>& nums) {
vector< int> arr;
arr.reserve(nums.size());
for (auto& num : nums) {
auto ptr = ranges::lower_bound(arr.begin(), arr.end(), num);
if (ptr == arr.end()) {
arr.push_back(num);
} else {
*ptr = num;
}
}
return arr.size();
}
};
然後是 Python 的 bisect.bisect_left()
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
arr = []
for num in nums:
i = bisect.bisect_left(arr, num)
if i == len(arr):
arr.append(num)
else:
arr[i] = num
return len(arr)
然後是 Go 的 sort.Search()
func lengthOfLIS(nums []int) int {
arr := make([]int, 0, len(nums))
for _, num := range nums {
idx := sort.Search(len(arr), func(i int) bool {
return arr[i] >= num
})
if idx == len(arr) {
arr = append(arr, num)
} else {
arr[idx] = num
}
}
return len(arr)
}
最後是 Rust 的 binary_search
impl Solution {
pub fn length_of_lis(nums: Vec< i32>) -> i32 {
let mut arr = Vec::with_capacity(nums.len());
for num in nums {
let i = match arr.binary_search(&num) {
Ok(index) => index,
Err(index) => index,
};
if i == arr.len() {
arr.push(num);
} else {
arr[i] = num;
}
}
arr.len() as i32
}
}
每種程式語言使用方式都有所不同。
訂閱：
意見 (Atom)