Instructions and Information
All the instruction of requesting a prototype, how the website works and other information can be find in this category.
Recursion vs Dynamic Programming
剛剛我在寫 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 加速器 Cheat Code (C++)
最近因為工作面試的關系,我都在練習寫 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…
淺談 CSRF 與 CSRF Middleware
最近在我的 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 的設計從一開始就按著標準的…
10 分鐘設定好 open web-ui 跟 ollama
open web-ui 是一個很方便的界面讓你可以像用 chat-GPT 那樣去跟 ollama 運行的模型對話。由於我最近收到一個 Zoraxy 的 bug report 指 open web-ui 經過 Zoraxy 進行 reverse proxy 之後出現問題,所以我就只好來裝裝看看並且嘗試 reproduce 出來了。 安裝 ollama 我這裡用的是 Debian,首先第一件事要做的當然就是安裝 ollama。教學在他們的網上有我這裡就直接寫 code 出來了。 https://ollama.com/download/linux curl -fsSL https://ollama.com/install.sh | sh 在執行這個 bash script 之後它會自動建立一個 systemd 的服務。預設 ollama 的 web server 只能透過 localhost loopback interface 存取,如果要透過其他網絡才能存取到 ollama 的 API 的話,我們就要讓它同時 listen to 其他的 network interface。最簡單直接的方式是把預設的 systemd service 檔案改成這樣: sudo systemctl stop ollama.service sudo systemctl edit ollama.service 然後在 service 檔案裡加入下面那行(見備注) ### Editing /etc/systemd/system/ollama.service.d/override.conf ### Anything between here and the comment below will become the new contents of the file # 加入下面這兩行 [Service] Environment="OLLAMA_HOST=0.0.0.0:11434" #下面的不要碰 ### Lines below this comment will be discarded ### /etc/systemd/system/ollama.service # [Unit] # Description=Ollama Service # After=network-online.target # # [Service] # ExecStart=/usr/local/bin/ollama serve # User=ollama # Group=ollama # Restart=always # RestartSec=3 # Environment="PATH=/usr/local/bin:/usr/bin:/bin:/usr/local/games:/usr/games" # # [Install] # WantedBy=default.target 儲存並退出之後重啟 ollama systemd 服務 sudo systemctl start ollama.service 抓模型 因為我比較喜歡用 CLI,所以我就直接透過 ssh 來順便把模型也載下來。這裡我在試玩的是 qwen:https://ollama.com/library/qwen 一般模型也會有不同大小,而我選這個是因為我要省空間(對,SSD 快要炸了),所以我就選了比較小的 1.8b 版本。你可以用這個指令來讓 ollama 準備這個模型: ollama run qwen:1.8b 如果要其他大小的模型的話,只要把後面的 1.8b 換成 4b / 7b 之類的就好了。另外比較有名的包含 llama3 之類也是可以透過這樣的方式下載。 值得一提 如果你的 root disk (Linux 的 / 或是 Windows 的 C: 硬碟)不夠空間跑你想測試的模型,你可以在啟動 ollama…
SEO 快速上手筆記
作為經營好幾個中小型的 Open Source Project website 的開發者,間中也會收到一些來自不同國家的 SEO 公司的垃圾郵件,說甚麼可以幫你把網站最佳化到上 Google 首頁結果之類的。首先,有幾點我要先說明 沒人知道 Google 的 Search Engine 排名演算法,而且很可能他們也是用 AI 來做的,他們自己的員工也不知道SEO 本身只是在 HTML file 的 head section 裡加一些 metadata 等級的簡單作業而已。就算要弄的話如果本身你會一點 HTML 跟知道要加甚麼 meta tag 的話其實也就一兩個小時的工作量就能做到外面公司的 80 - 90% 有效度。想在 Google 出第一個結果的最佳方法是幫你的產品改一個 Google Search 沒結果的名字(真的,不相信的話你去 Google 找 "Zoraxy" 看看,第一項應該就會出現我的 Zoraxy project 了,而那個 github page 根本除了 OG 以外沒做 SEO) 那正文要來了囉 HTML Head 結構 HTML Header 是一個簡單的 HTML tag。一般的話大概長這樣 <!DOCTYPE html> <html> <head> <!-- 這裡就是 Head 的部分--> </head> <body> </body> </html> 那一個完整,有做 SEO 的 head 會長怎樣呢?我們來看這個範例 <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> <meta name="viewport" content="width=device-width, initial-scale=1"> <meta name="format-detection" content="telephone=no,email=no,address=no"> <title>托比的神奇蹦蹦主頁</title> <!-- HTML Meta Tags --> <title>imuslab</title> <meta name="description" content="創客產品與開源軟體項目,還有方便好用的各種網上小工具 | Archive of tobychui's maker products and open source projects, with online tools and service for myself but also for anyone who visited my site"> <!-- Facebook Meta Tags --> <meta property="og:url" content="https://imuslab.com"> <meta property="og:type" content="website"> <meta property="og:title" content="imuslab"> <meta property="og:description" content="創客產品與開源軟體項目,還有方便好用的各種網上小工具 | Archive of tobychui's maker products and open source projects, with online tools and service for myself but also for anyone who visited my site"> <meta property="og:image" content="https://imuslab.com/index/og.png"> <!-- Twitter Meta Tags --> <meta name="twitter:card"…
Concurrent & Racing Conditions (並發與競態條件)
最近因為我在開發 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 鎖上了…
在 Linux 上建立一個有容量限制的資料夾
最近我在研究 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 裡看到掛載的虛擬硬碟 /…
Golang 程序連續執行一個月之後一定會出錯之神奇原因及除錯
話說半年前我開發了一個叫 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 也不怎麼意外就是了)
ESP8266 讀取 SD 卡太慢?要試試全速 SPI 嗎?
我看到日本技術宅的 Blog ,覺得奇怪這裡為甚麼他可以在 SD.begin 後面設定一個指定的速度(? https://www.mgo-tec.com/blog-entry-esp8266-wroom-spi-speed-up.html 於是我跑去翻 ESP8266 Arduino Core 的源碼,原來 ESP8266 比起原生的 Arduino core 在 SD.begin function call 多了一個可選擇指定的 uint32_t 參數,預設是 SPI 一半速度(4 Mhz),但是如果你的 SD 卡夠快(例如說現在大部分 A1 Class 10 的卡)都可以上到 8Mhz (SPI Full Speed) 或以上(這裡日本部落格用的是 40Mhz,為了資料安全好孩子不要隨便超頻你的 SD 卡) https://github.com/esp8266/Arduino/blob/313b3c07ecccbe6fee24aa9fa447c4aed16ca499/libraries/SD/src/SD.h#L35 嘛不過 ESP8266 的 WiFi 速度極限也就 4Mbps,如果要用來做網頁伺服器的話 SPI 速度設定到全速(8Mhz)已經足夠盡用它的網絡速度了。 備注:如果要設定速度的話可以用 ESP8266 SD library 內預設的常數 uint32_t const SPI_FULL_SPEED = 8000000; uint32_t const SPI_HALF_SPEED = 4000000; uint32_t const SPI_QUARTER_SPEED = 2000000;
在 Raspberry Pi Zero 2W 上設定 WiFi AP 作為 WiFi 中繼器
因為不知道為甚麼網上沒有 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…