這一篇筆記主要是為了 lab: network driver 中，要我們先讀一下 xv6 book ch5: Interrupts and device drivers，這篇文章是我自己的筆記 Interrupts and device drivers Driver 需要了解 device 的 interface，可能很複雜或是文件寫得很差 Device 通常可以製造一些 interrupt, 在 xv6 中，這在 devintr() 中處理 kernel/trap.c: devintr(): 像是這裡回傳是否為 device interrupt // check if it's an external interrupt or software interrupt, // and handle it. // returns 2 if timer interrupt, // 1 if other device, // 0 if not recognized. int devintr() { uint64 scause = r_scause(); if((scause & 0x8000000000000000L) && (scause & 0xff) == 9){ // this is a supervisor external interrupt, via PLIC. // irq indicates which device interrupted. int irq = plic_claim(); if(irq == UART0_IRQ){ uartintr(); } else if(irq == VIRTIO0_IRQ){ virtio_disk_intr(); } #ifdef LAB_NET else if(irq == E1000_IRQ){ e1000_intr(); } #endif else if(irq){ printf("unexpected interrupt irq=%d\n", irq); } // the PLIC allows each device to raise at most one // interrupt at a time; tell the PLIC the device is // now allowed to interrupt again. if(irq) plic_complete(irq); return 1; } else if(scause == 0x8000000000000001L){ // software interrupt from a machine-mode timer interrupt, // forwarded by timervec in kernelvec.S. if(cpuid() == 0){ clockintr(); } // acknowledge the software interrupt by clearing // the SSIP bit in sip. w_sip(r_sip() & ~2); return 2; } else { return 0; } } 許多 device driver 分為兩個部份： process’s kernel thread interrupt time 接著分別使用 Console input/output 來看 driver 如何運作 ...

Initialize 我們首先觀察 lab net 所提供的初始化過程，大致上了解要如何從 E1000 manual 轉換到程式碼 kernel/main.c: main() kernel/pci.c: pci_init() kernel/e1000.c: e1000_init(uint32 *xregs) regs[XXX] = OOO kernel/sysnet.c: sockinit() initlock() kernel/pci.c: pci_init() void pci_init() { // we'll place the e1000 registers at this address. // vm.c maps this range. // 我們會把 e1000 registers 放到這個位置 // 如下圖，他會被放在 unused and other I/O devices 的區塊 // vm.c 會負責做這個 mapping uint64 e1000_regs = 0x40000000L; // qemu -machine virt puts PCIe config space here. // vm.c maps this range. // 這裡則是在 mapping PCIe config // 跟前面一樣，是放在 unused and other I/O devices 的區塊 // ECAM for Extended Configuration Access Mechanism uint32 *ecam = (uint32 *) 0x30000000L; // look at each possible PCI device on bus 0. // bus == 0 是固定的，只掃描 Primary Bus // dev: 0 ~ 31 設備號碼，每一個代表一個獨立設備例如 E1000 網卡、顯示卡，現在要尋找 E1000 // func: 功能號碼，每一個設備可以有多個 function, 這裡只需要尋找第 0 個功能，E1000 也只有一個功能 // offset: 指向配置空間中特定 4 位元組暫存器的偏移量, 設為 0 // off: 透過上面的資訊取得總 offset for(int dev = 0; dev < 32; dev++){ int bus = 0; int func = 0; int offset = 0; uint32 off = (bus << 16) | (dev << 11) | (func << 8) | (offset); volatile uint32 *base = ecam + off; uint32 id = base[0]; // 100e:8086 is an e1000 if(id == 0x100e8086){ // command and status register. // bit 0 : I/O access enable // bit 1 : memory access enable // bit 2 : enable mastering base[1] = 7; __sync_synchronize(); for(int i = 0; i < 6; i++){ uint32 old = base[4+i]; // writing all 1's to the BAR causes it to be // replaced with its size. base[4+i] = 0xffffffff; __sync_synchronize(); base[4+i] = old; } // tell the e1000 to reveal its registers at // physical address 0x40000000. base[4+0] = e1000_regs; e1000_init((uint32*)e1000_regs); } } } ...

Lab 連結：Lab net: Network driver Background You’ll use a network device called the E1000 to handle network communication. To xv6 (and the driver you write), the E1000 looks like a real piece of hardware connected to a real Ethernet local area network (LAN). In fact, the E1000 your driver will talk to is an emulation provided by qemu, connected to a LAN that is also emulated by qemu. On this emulated LAN, xv6 (the “guest”) has an IP address of 10.0.2.15. Qemu also arranges for the computer running qemu to appear on the LAN with IP address 10.0.2.2. When xv6 uses the E1000 to send a packet to 10.0.2.2, qemu delivers the packet to the appropriate application on the (real) computer on which you’re running qemu (the “host”). ...

題目連結：136. Single Number 解題思路 這題是一個蠻神奇蠻剛好的一題，同時使用了 xor 與「出現兩次」這兩個元素，因為 同一個數字 xor 在一起會變成 0 這題就用這樣的特性解決 程式碼 class Solution { public: int singleNumber(vector<int>& nums) { int n = 0; for (int num : nums) n ^= num; return n; } };

題目連結：746. Min Cost Climbing Stairs 解題思路 這題利用 DP 的方式，「有了前兩天的資訊可以推測出今天」依此類推的得知最後的答案。 程式碼 class Solution { public: int minCostClimbingStairs(vector<int>& cost) { int n = cost.size(); vector<int> dp(n, 0); dp[0] = cost[0]; dp[1] = cost[1]; for (int i = 2; i < n; i++) dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]; return min(dp[n - 1], dp[n - 2]); } };

題目連結：1004. Max Consecutive Ones III 解題思路 這題使用兩個 pointer left 與 right 來紀錄當前的 array 大小，像是： 0 1 2 3 4 5 6 7 8 9 ↑ ↑ l r 這個時候 left == 2, right == 6 長度的計算為 length = right - left + 1 也就是 6 - 2 + 1 == 5 如何表達 length == 0 這樣的設計會碰到的下一個問題是 假設 right == 6 如何表達 length == 0 的情況?? 會像是下面這個樣子： 0 1 2 3 4 5 6 7 8 9 ↑ ↑ r l 雖然是 left 不過卻在 right 的右邊，但這樣做的好處就在於我們計算長度的公式： ...

題目連結：1679. Max Number of K-Sum Pairs 解題思路 這一題跟 11. Container With Most Water 的感覺還蠻像的，都是先把兩的 pointer 放在兩端，並且根據不同的情況，用 greedy 的方式判斷下一步要做什麼。還有這個問題是配對到了就刪除掉，所以也不會有重複的問題。 程式碼 class Solution { public: int maxOperations(vector<int>& nums, int k) { int left = 0; int right = nums.size() - 1; int count = 0; sort(nums.begin(), nums.end()); while (left < right) { if (nums[left] + nums[right] == k) { count++; left++; right--; } else if (nums[left] + nums[right] < k) { left++; } else { right--; } } return count; } };

題目連結：345. Reverse Vowels of a String 解題思路 這題就很直覺得掃過兩遍，第一遍收集 Vowels，第二變把 Vowels 用相反的順序放回去，真有什麼好說的東西的話應該是寫個 helper function isVowels() 會方便一些。 程式碼 class Solution { private: bool isVowels(char c) { if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true; if (c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U') return true; return false; } public: string reverseVowels(string s) { int n = s.size(); queue<char> q; for (int i = 0; i < n; i++) if (isVowels(s[i])) q.push(s[i]); for (int i = n - 1; i >= 0; i--) if (isVowels(s[i])) { s[i] = q.front(); q.pop(); } return s; } };

題目連結：334. Increasing Triplet Subsequence 解題思路 這題我剛開始是朝著先找出 i 與 k 之後再檢查 j 是否存在，想了幾遍都覺得有些瑕疵，後來發現依照 i, j, k 的順序尋找會比較合理一些，可以用很 greedy 的方式去尋找。 如果再來一次的話，我應該會先列出以下兩種可能： 先找出最大最小的 i 與 k, 再找出中間的 j 依照順序尋找 i, j, k 評估之後挑選較有可能的順序，並且保持另一個方案的可能性。 程式碼 class Solution { public: bool increasingTriplet(vector<int>& nums) { if (nums.size() < 3) return false; int i = 0; int j = -1; for (int l = 1; l < nums.size(); l++) { if (nums[l] < nums[i]) { i = l; } else if (j > 0 && nums[l] > nums[j]) { return true; } else if (nums[l] > nums[i]) { j = l; } } return false; } };

sudo apt-get update sudo apt-get install -y kubelet kubeadm kubectl sudo apt-mark hold kubelet kubeadm kubectl https://stackoverflow.com/questions/52893111/no-endpoints-available-for-service-kubernetes-dashboard nodes: https://120.108.205.137:9999/ui/ 192.168.1.115 ssh k1 # ssh [email protected] ssh k2 # ssh [email protected] ssh k3 # ssh [email protected] ssh k4 # ssh [email protected] sudo vim /etc/hosts # /etc/hosts 192.168.1.115 asus 192.168.1.11 k1 192.168.1.12 k2 192.168.1.13 k3 192.168.1.14 k4 # for cluster on virtualbox 192.168.56.1 thinkpad # my thinkpad 192.168.56.101 node1 # vm on virtualbox sudo systemctl restart systemd-resolved docker installation https://docs.docker.com/engine/install/ubuntu/ CRI (container runtime interface) 是 container 用來互相溝通的 API ...