剛剛我在寫 Leetcode 的 70. Climbing Stairs 沒留意到它是考 DP 寫成了 Recursion，結果跑起來 timeout。剛好我覺得這是一個很好的 Recursion vs DP 的範例，我就拿出來解釋一下好了。首先，這是我寫的 Recursion 解法： class Solution { public: int sol = 0; int climbStairs(int n) { f(n, 0); //把 sum 設為 0 return sol; } void f(int n, int sum){ if (sum > n) return; //超出了目標位置 if (sum == n){ sol++; //這是其中一個爬法 return; } //跟終點還有點距離，試試 f(n, sum+1); //爬一步 f(n, sum+2); //爬兩步 } }; 每爬一段之後，檢查是不是已經到終點了，如否，再分支出兩種走法 - 走一步 與 走兩步。 這個我覺得是最簡單易懂的寫法（甚至已經是教科書等級的 recursive function 了），但是居然跑到 timeout 這個我還真的沒想到。所以後來只好換成 space-time tradeoff 的 dynamic programming 寫法： class Solution { public: int climbStairs(int n) { int dp[46]; //因為題目說最多 n = 45 dp[1] = 1; //爬到第一格，只有一個爬法就是爬一格 dp[2] = 2; //爬到第二格，只有 1 + 1 跟 2 兩種爬法 for(int i = 3; i <= n; i++){ //從 3 開始，就是前兩格爬法的總和 dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; // 最後回傳能爬到最後一格的總可能路線 } }; 果然是做嵌入式開發做得多，寫出來都是以最佳化 memory consumption 的職業病（

最近因為工作面試的關系，我都在練習寫 Leetcode （畢竟從大學畢業之後我的主力語言都是 C （MCU / low level）、Go （Linux / Networking Applications）跟 網頁（HTML 、CSS 、JS 那堆）。雖然我都跟我面試的主管說「我都沒在寫 Leetcode」（因為我不想他們以「平常有寫多少 Leetcode 」為顧用考慮之一），但是或多或少因為有一段時間沒寫 C++ 了所以還是要找些免費題目來抓回以前的感覺。 最近我在寫 LeetCode 的時候發現一個滿有趣的現像，就是一般很多題目都會有一些特別特殊的極端例子（超快、或是超省記憶體）的情況。去翻一翻這些 code sample 之後我發現了一段很有趣的 code。 int speedUp = [] {std::ios::sync_with_stdio(0); std::cin.tie(0); return 0; }(); bool has[100002]; int digit(char c) { return c & 15; } bool isDigit(char c) { return '0' <= c && c <= '9'; } int init = [] { std::ofstream out("user.out"); std::cout.rdbuf(out.rdbuf()); for (string s; std::getline(std::cin, s); std::cout << '\n') { int n = count(s.begin(), s.end(), ',') + 3; memset(has, 0, n); for (int _i = 1, _n = s.length(); _i < _n; ++_i) { if (s[_i] == '-')for (_i += 2; isDigit(s[_i]); ++_i); else { int v = s[_i++] & 15; while (isDigit(s[_i])) v = v * 10 + digit(s[_i++]); if (0 < v && v < n) has[v] = true; } } for (int i = 1;; ++i) if (!has[i]) { std::cout << i; break; } } exit(0); return 0; }(); 沒錯，是一段 C++ 的 runtime cheat code。先上面的部分開始看，這邊它使用了 lambda function 來透過「假裝」定義 speedup variable 來執行了一些 STDIO redirect 的功能。我猜它應該是把之後執行的東西的 STDOUT 跟 parent 的 STDIN…

最近在我的 Zoraxy 開源專案那邊出現了這樣的一個 bug issue 他還很好的附了一個網頁測試介面的截圖 甚麼是 CSRF 攻擊？ CSRF（Cross-Site Request Forgery，跨站請求偽造）是一種網絡攻擊技術，攻擊者通過在受害者不知情的情況下，冒充受害者的身份在受害者已經認證的網站上執行未經授權的操作。 CSRF 攻擊的工作原理 受害者登錄到可信網站：受害者首先登錄到一個需要認證的網站，在這例子是 Zoraxy 的後台管理頁面攻擊者製造惡意請求：攻擊者創建一個包含惡意請求的網頁或電子郵件，例如說這裡的一個 free burger 網頁 html + web form （action 或 form submit URL 指向 Zoraxy 的後台管理頁面）受害者訪問惡意鏈接：受害者在登錄狀態下 request 了攻擊者控制的網頁並提交了 web-form。執行未經授權的操作：由於受害者已經登錄（Auth Cookie 會跟著 form 一起送出去），Zoraxy webmin 介面會以為這些 request 是 valid 的，並執行相應的操作，例如上面例子的 toggle proxy 開關狀態 。 防禦 CSRF 攻擊的方法 CSRF Token：在每個受保護的操作請求中加入隨機生成的、唯一的 CSRF Token，並驗證這些 Token 以確保請求是合法的。檢查 Referer 和 Origin 頭：檢查 HTTP 頭中的 Referer 和 Origin 字段，確保請求是從合法的來源發出的。但是我在寫的是 Reverse proxy，本來 Referer 跟 origin 就是不可信的，所以不能使用此方法。雙重提交 Cookie：將 CSRF Token 存儲在 Cookie 中，並在請求中一起提交和驗證。使用 SameSite Cookie 屬性：設置 Cookie 的 SameSite 屬性為 Strict 或 Lax，限制跨站請求攜帶 Cookie。 說真的這也不是我第一次處理 csrf 問題。先前同一位使用者也對 ArozOS 提出過類似的 issue report。然而 ArozOS 因為是使用 agile 開發的，API 散落得到處都是，根本沒辦法用標準的方式來做 csrf middleware 來保護 API 接口，所以當時只用了一個非常不標準的方式來做（就是每一個 post request 之前都加一個要求 csrf token 的 ajax request，變成每個 request 都會變成要 request 2 次） csrf middleware csrf middleware 是一個 http Handler 並讓它來對 request 進行預處理並對不合規格的 POST (PUT / DELETE) 等 request 進行攔阻。所以這裡有兩個需要做的事情 在 HTML 頁面生成的時候，在頁面上加入一個 csrf token在有資料需要以 POST 等 request 回傳到伺服器時，在 payload 中以 header field 的方式附上頁面的 csrf token 在 ArozOS 的做法上，它是先對伺服器進行一個 csrf token generation request，然後再把 request 附到下一個 ajax POST request 裡面。這做法雖然不是不行，但是對於前端來說要改實在太複雜，而且一個 csrf token 又沒有那麼快 expire，不斷生的話只會浪費後端資源。 Production grade 的 csrf middleware 使用方法 由於 Zoraxy 的設計從一開始就按著標準的…

最近因為我在開發 Zoraxy 時需要設計一個可以做到 high speed concurrent READ 跟間中 write 的 map，跟另一位高雄的工程師大佬討論了一個晚上，後來我發現原來滿多人對 concurrent / racing conditions 的處理有一定程度的誤解，所以我就來簡單的解釋一下最常見的誤解 - Check for locking。 問題 假設你有兩個 process，一邊要讀取一個無法同時讀寫的 map 資料結構（例如 Go 的 map[string]struct{}），另一個要寫入新的 key 到同一個 map。由於 map 並沒辦法處理 concurrent R/W，所以你要怎樣做呢？ 解決方法 1：改用專用的 concurrent map （如 Go 的 sync.Map） 這個解決方法簡單直接，我就不再詳細解釋了。然而由於我在開發 Zoraxy 的 high concurrent access 特質，使用 sync.Map 的話會做成很高的 over-head，因此我並不是很想用它（但是也不影響 sync.Map 作為沒法解決時用的最後方案的決定） 解決方法 2：mutex lock 這算是比較正規的方案之一。在讀取和寫入之前先對 map (或是 slice) 進行鎖定，然後在寫入或讀取之後解鎖。這樣就能確保同時間只有一個 process 對這個 map 有 R/W access。但是這同時也會產生另一個問題，就是在 read lock 了之後，假設有另一個 process 也想同時進行讀取的話就必須要等前面的讀完，因此這個方案對於高並發的 request handling 來說並不是太有效率。 那聽到這裡的時候很多人會直覺的覺得：那只有 write 的時候 lock 就好啦，read 的時候檢查 map 是不是被 lock，沒 lock 的話就讀取。由於檢查的時候不會 lock，因此其他需要 read 的 process 也不會被擋不是嗎？ 聽上去好像沒錯喔？讓我簡單寫一個 pseudocode 例子： function write(){ mutex.lock() map.write("foo", "bar") mutex.unlock() } function read(){ if (!mutex.isLocked()){ //Map is not locked var value = map.read("foo") print(value) }else{ //Map is locked, retry after 100ms delay(100) read() } } mutex 的部分可以是 programming language 自帶的 mutex 功能或是簡單的 boolean，效果都是一樣的。但是如果你有注意到，你不會找到 mutex.isLocked() 這個功能。 如果你需要用到這個，很大機會你寫錯了 這是為甚麼呢？那是因為 OS 層基本運作原理所引起的。這裡對於本科沒修 Computer Architecture （計算機架構）的工程師可能比較難理解。簡單來說就是，CPU 上就只有 n 個核心，但是你的作業系統上面有很多東西在執行，所以 OS 會對上面執行的工作（process）進行快速切換。每次切換的時候因為速度很快，所以會讓你有一種它們在並行處理的感覺。而實質上，每個 process switching 都會有一個 overhead，而這個 overhead 就是為甚麼 mutex lock 沒辦法被用於檢查的原因。 其中一種常用的 scheduling 演算法：Round Robin Process Switching 關於 CPU scheduling 跟 scheduling 演算法的詳情可以看這邊 所以為甚麼 Mutex 不能檢查是不是被其他 process 鎖上？ 當你去檢查一個 mutex 是否被鎖的時候，檢查當下可能沒被鎖，但是檢查完到執行下一個邏輯的時候可能已經被另一個 process 鎖上了…

最近我在研究 mdadm 的時候無意中發現了一個可以依靠 losetup 和 partition 映像檔的神奇方法來建立一個具有容量限制的資料夾。所以就寫這篇來簡單記錄一下。 好，可是這有甚麼用？ 之前我在開發 ArozOS 的時候想著給使用者建立一個 storage quota。本來想著用 linux 的 File System 來 implement 這個功能，可是找了很久之後發現方法都很麻煩或是過於複雜（例如依賴一些特別的 file system format / container）。所以如果剛好你想設置一個 hard limit 給一些軟體來做 buffer / upload 之類的，都可以考慮這個方法。 首先，建立一個映像檔 我們第一件事情要做的就是建立一個固定大小的映像檔。以我這裡為例，我建立了一個 64MB 的映像檔來模擬一個硬碟 partition。 bs 是 block size，就是系統會 buffer 多少 data 才會真正寫進去這個（block ）device，這裡用的是 4MB。 count 是這個虛擬硬碟裡有多少個 block，16 個 4MB 的 block 加起來就是 64MB 啦 sudo dd if/dev/zero of=sdX.img bs=4M count=16 至於 /dev/zero 是甚麼，它是一個只會不斷吐出 0 的 byte stream。你可以把它當成一個無限大的檔案，裡面只存在無限個 0。透過 dd 指令，我們就可以把需要的 0 bit 從這個檔案裡 clone 出來來建立我們需要的映像檔大小。 之後：建立檔案系統 在建立了一個空白的映像檔之後，透過 ls 指令我們可以看到新鮮的 .img 檔出現了。 aroz@orangepizero2:~/raidtest$ ls sdX.img 然後我們就是需要對它進行格式化，就古人所說 Everything is a file Linus Torvalds did not say this 所以我們可以直接對它用 mkfs 跟 mount 指令。假設我們有一個叫 sdX/ 的資料夾，那我們就可以把映像檔格式化之後掛到那個資料夾。 // 建立掛載點 aroz@orangepizero2:~/raidtest$ mkdir sdX //用 ext4 把映像檔格式化 aroz@orangepizero2:~/raidtest$ sudo mkfs.ext4 sdX.img mke2fs 1.47.0 (5-Feb-2023) Discarding device blocks: done Creating filesystem with 65536 1k blocks and 16384 inodes Filesystem UUID: bf600d34-c93a-48bc-ad27-27255fbd1333 Superblock backups stored on blocks: 8193, 24577, 40961, 57345 Allocating group tables: done Writing inode tables: done Creating journal (4096 blocks): done Writing superblocks and filesystem accounting information: done //檢查看看是不是需要的資料夾和檔案都存在 aroz@orangepizero2:~/raidtest$ ls sdX sdX.img //把映像檔掛上去 aroz@orangepizero2:~/raidtest$ sudo mount sdX.img ./sdX 之後我們就可以在 df 裡看到掛載的虛擬硬碟 /…

話說半年前我開發了一個叫 imusutm 的 Simple Up Time Monitor。它是一個很簡單的程式：每隔 5 分鐘去 ping 一次 json 設定檔案裡面的網址，然後把它 buffer 到 RAM。同時提供一個 RESTFUL API 給 php script 來 call 並回傳最近一天的狀態。 可是不知道為甚麼，這程式很固定每隔一個月就會出現全部斷線的狀態，連帶用這系統的 Telegram bot 也一律全部報錯 在無論如何都沒辦法在本地端 reproduce 之後，在上一個月我把所有 error 裡都加入了 error message print-out 來協助除錯。結果被我發現問題了： 2023/02/24 20:20:34 Get "{某個要 ping 的 IP 地址}": dial tcp {某個要 ping 的 IP 地址}: bind: An operation on a socket could not be performed because the system lacked sufficient buffer space or because a queue was full. 一看到這個我就明白了，原本是 socket 用光了。可是一台主機的 socket 有這麼多怎可能能全部佔用？ 原來是忘記了 resp.Body.Close() 於是我去看整段 code 唯一有用到 socket 的部分：http.Get(url)，發現忘記了寫 resp.Body.Close() 了（222 行是新加入的），所以難怪會出現這個問題。 可是，又為甚麼是大約一個月會出現一次？ Windows 的 Dynamic Port 與 ArozOS Windows 的 dynamic port range 是由 49152 到 65535。雖然有一些間中會被佔用，但是大部分都是用完之後就會被釋放出來。這兩個數字相減之後便能得出 16384 個能用的 dynamic port。 至於為甚麼是一個月？因為 每小時有 12 個 5 分鐘 x 一天 24小時 x 30天 = 8640 個 connection，然後由於 ArozOS 使用的 Go net/http 會自動斷開，而這數字又差不多是可用 port 數的一半，再加上列表上又剛好只有兩個 connection 是能維持的，我好像猜到點甚麼的樣子（？ 總括而言 相信加入了 resp.Body.Close() 之後就能解決 utm 不穩定的問題了，如果下一個月再出現類似的問題我還是整個砍掉重寫好了（畢竟這只是一個我在等上飛機時的小作品，出現這些奇怪的 bug 也不怎麼意外就是了）

因為不知道為甚麼網上沒有 Raspberry Pi Zero 2W 以外接 WiFi USB 作為 WiFi 中繼器的教學，所以我就來自己研究出一個方法囉 材料 Raspberry Pi Zero 2WRaspberry Pi OS 用作 wlan1 的 USB WiFi 模組 安裝所需 Package sudo apt-get update sudo apt-get upgrade sudo apt-get install hostapd sudo apt-get install dnsmasq sudo systemctl stop hostapd sudo systemctl stop dnsmasq 設定網絡界面卡 sudo mv /etc/dnsmasq.conf /etc/dnsmasq.conf.orig sudo nano /etc/dnsmasq.conf 寫入以下內容 interface=wlan1 dhcp-range=192.168.0.11,192.168.0.30,255.255.255.0,24h 固定 wlan1 的 IP 地址 sudo nano /etc/network/interfaces 把 source /etc/network/interfaces.d/* 加上 comment： #source /etc/network/interfaces.d/* 寫入以下內容 auto lo iface lo inet loopback auto wlan0 iface wlan0 inet dhcp allow-hotplug wlan1 iface wlan1 inet static address 192.168.0.10 netmask 255.255.255.0 broadcast 192.168.0.255 gateway 192.168.0.254 設定 Hostapd sudo nano /etc/hostapd/hostapd.conf 寫入以下內容（記得更新 WiFi 名稱與密碼） interface=wlan1 hw_mode=g channel=7 wmm_enabled=0 macaddr_acl=0 auth_algs=1 ignore_broadcast_ssid=0 wpa=2 wpa_key_mgmt=WPA-PSK wpa_pairwise=TKIP rsn_pairwise=CCMP ssid=[WiFi SSID 名稱] wpa_passphrase=[WIFI 密碼] 之後編輯預設設定 sudo nano /etc/default/hostapd 把原本的 #DAEMON_CONF="" 改成 DAEMON_CONF="/etc/hostapd/hostapd.conf" 設定 wlan1 -> wlan0 的 forwarding sudo nano /etc/sysctl.conf 把 #net.ipv4.ip_forward=1 改成 net.ipv4.ip_forward=1 新增 iptables 規則 如果你是用 Lite 版沒有 iptables 可以先透過以下指令安裝 sudo apt-get install iptables 然後輸入 sudo iptables -t nat -A POSTROUTING -o wlan1 -j MASQUERADE sudo sh -c "iptables-save > /etc/iptables.ipv4.nat" 編輯 rc.local 在啟動時自動應用規則 sudo nano…

因為間中要用到每次都要去 Stack Overflow 抓有點麻煩所以就直接記下來了： new Date().toLocaleDateString() > 2022/1/30 new Date().toLocaleString(undefined, {year: 'numeric', month: '2-digit', day: '2-digit', weekday:"long", hour: '2-digit', hour12: false, minute:'2-digit', second:'2-digit'}) > 2022年01月30日 星期日 01:05:48 new Date().toLocaleDateString('en-US', {year: 'numeric', month: '2-digit', day: '2-digit'}) > 01/30/2022 new Date().toLocaleDateString('en-ZA') > 2022/01/30 new Date().toLocaleDateString('en-CA') > 2022-01-30 new Date().toLocaleString("en-US", {timeZone: "America/New_York"}) > 1/29/2022, 12:05:48 PM new Date().toLocaleString("en-US", {hour: '2-digit', hour12: false, timeZone: "America/New_York"}) > 12

最近因為我在弄一個 60W 的 PD 充電器，然後想弄一個迷你的螢幕來顯示電池的資訊，所以我便選用了一個 2.2寸的 UART HMI 了。 2.2 寸的 UART HMI，比想像中要小一點 選 UART HMI 的原因有很多，網上也有很多文章教你怎樣選合適的螢幕，所以我就不細說了。簡單來說， UART HMI 是一種可以透過 Serial 來控制螢幕載入預先設計好的界面的一種人機界面。 發送指令到螢幕 HMISerial 是 Software Serial。以下 function 把 cmd 內的內容發到螢幕，如果 debugMode 被啟用，側會同步輸出到 hardware serial 上。 SoftwareSerial HMISerial(2, 3); // RX, TX //... void sendCommand(String cmd){ if (debugMode){ //Mirror output to serial Serial.print(cmd); Serial.write(0XFF); Serial.write(0XFF); Serial.write(0XFF); } HMISerial.print(cmd); HMISerial.write(0XFF); HMISerial.write(0XFF); HMISerial.write(0XFF); delay(50); } 使用例子： sendCommand("t0.txt=\"[info] MCU Connected\""); 取得現在 HMI 屏幕正在顯示的 Page ID 如果你把 sendme 指令發到屏幕，屏幕會回傳現在的 page ID 給你，它的回傳信號大約長這樣 66 01 FF FF FF 66 是這個指令的回傳碼，01 是現在的 page ID （即是 page 1），FF FF FF 側是傳送完成的意思，所以我們只需要在 Serial.read() 的時候抓到 0x66 就知道下一個一定是 page ID 了。 int getPageNumber(){ sendCommand("sendme"); bool nextReadIsPageNumber = false; while (HMISerial.available() ＞ 0) { // read the incoming byte: incomingByte = HMISerial.read(); if (nextReadIsPageNumber){ //這是 page ID nextReadIsPageNumber = false; return incomingByte; } if (incomingByte == 0x66){ //下一個出現的 byte 就是 page ID 了 nextReadIsPageNumber = true; } } } 使用例子（檢查現在是否在 page 0（hex: 0x00）） currentPageNumber = getPageNumber(); if (currentPageNumber == 0x00){ //Do something } 成果（Arduino 透過 COM port 輸入到模擬器）

在開發 aPrint 系統的時候，其中一個功能是使用 CSG 把兩個 Mesh 組合成一個容器。可是在組合匯出之後卻出現 face data 重疊的情況（也有人會把它叫做 z-fighting 或是 invalid normal ） 在 Windows 的 3D viewer 中可以看到全部面都有一些問題 這個我研究了一段時間，發現這是跟 extrude 模型的時候的設定有關。一般來說，為了避免模型在背面出現破圖，所以在 render 的時候也會把 rendering face 設成雙面。以下為其中一個例子 BABYLON.MeshBuilder.ExtrudeShape("container-outerwall", { shape: externalBorder, path: [extrusionStart,extrusionEnd], cap: BABYLON.Mesh.CAP_ALL, sideOrientation: BABYLON.Mesh.DOUBLESIDE }, scene); 可是這樣在 CSG 處理的時候卻會出現問題，我懷疑是與 Mesh.CAPALL 的設定有關，可是我並沒有深入研究是不是 CAP_ALL 設定了之後就不能使用 DOUBLESIDE 的設定。 然而在把sideOrientation 改成 FONTSIDE 之後問題就解決了。 BABYLON.MeshBuilder.ExtrudeShape("container-outerwall", { shape: externalBorder, path: [extrusionStart,extrusionEnd], cap: BABYLON.Mesh.CAP_ALL, sideOrientation: BABYLON.Mesh.FRONTSIDE }, scene); 所以結論就是如果你要進行 CSG 操作的話 sideOrientation 不要設成 DOUBLESIDE 就對了。