Hackpads are smart collaborative documents. .

陳婉雅

759 days ago
學組語的目的之一: 判斷compiler產生結果是否正確 & Google 偷到的程式是否有效益
 
An example of pipeline problem: arm與cortex筆記 
 
  • 測驗 + 模擬面試題目分析 (Part I)
給定opendir() + readdir(), 利用遞迴寫出類似find()的程式.
[Homework] 寫出非遞迴版本
Jim H 思考:對 file system 操作的效率
 
 
 
Linux上有實作 IRQ-safe Spin Locks , 此部份會disable all interrupts在local CPU
semaphore
類似計數器概念, 限制數量存取某一段資源
binary semaphore (解鈴還需繫鈴人) 
謝 凱
  • 有owner -> 解鈴還需繫鈴人
Chi L
  • 這譬喻是只有owner的,放錯邊了
謝 凱
  • 感謝指正!
  • preemptiable?
沒有owner的概念, 任何的 thread都可能lock(0)/unlock(1)
mutex
指允許同一時間只有一個process可以存取某一塊資料 (有保護的功能), 只有鎖住的process才可以解鎖 (有owner概念)
 
 
Jim H reference:
 
 
 
 
陳婉雅 課堂關鍵字&提問
p.29 一般類型的虛擬化
p.31 sensitive instruction / privileged  instruction
p.32 vitrualization的分類
p.43 binary translation / hypercall
p.38 problematic instructions
p.42 解法: hardware or software(compiler)
p.45 hypercall (把有問題的指令換掉)
p.47 xvisor : 修改elf執行檔的內容, 把有問題的指令換掉
p.52 IPA : translate virtual memory to physical memory : 三層結構
p.62 ARM
謝 凱 p.64 IPA: compatible to each Guest OS
陳婉雅
  • 關鍵字: ksm linux
p.66 不能給gusetOS拿到的IRQ : 例: GPU, 網路
p.67
  • 關鍵字: hsa dsp gpu
p.69 OKL4 => sel4 (open source)
謝 凱 p.70 開發Xen-ARM的driver要寫三個drivers: Frontend, Backend and Native Drivers
陳婉雅 關鍵字: qualcomm amss
p.72-73 event channel : 跨越hypervisor通訊 : 類似系統呼叫
 VMExit => 讓guest OS直接使用硬體資源
p.75-76 big.LITTLE : CPU migration中間發生的interrupt => hypervisor處理
謝 凱 p.76 有些interrupt非有效的,或需要更高的權限來處理
陳婉雅 p.80 microhypervisor
關鍵字: sel4 virtualization
p.84 issues : performance (特別是system call)
power consumption
p.86 應用
例: Firmware OTA
faster device boot time (關鍵字: 羅習五 中正 快速開機)
 
  • 測驗 + 模擬面試題目分析 (Part II)
Jim H 給定每個 pixel 為 32-bit 的 RGBA 的 bitmap,其轉換為黑白影像的函式為:
  • void rgba_to_bw(uint32_t *bitmap, int width, int height, long stride) {
  •     int row, col;
  •     uint32_t pixel, r, g, b, a, bw;
  •     for (row = 0; row < height; row++) {
  •         for (col = 0; col < width; col++) {
  •             pixel = bitmap[col + row + stride / 4];
  •             a = (pixel >> 24) & 0xff;
  •             r = (pixel >> 16) & 0xff;
  •             g = (pixel >> 8) & 0xff;
  •             b = pixel & 0xff;
  •             bw = (uint32_t) (r * 0.299 + g * 0.587 + b * 0.114);
  •             bitmap[col + row * stride / 4] = (a << 24) + (bw << 16) + (bw << 8) + (bw);
  •         }
  •     }
  • }
請提出效能改善的方案:
  • 建立表格加速浮點數操作 (L1 cache?)
  • 減少位移數量
 
Hint: bwPixel = table[rgbPixel & 0x00ffffff] + rgbPixel & 0xff000000;
==> 16 MB
 
Hint:
bw = (uint32_t) mul_299[r] + (uint32_t) mul_587[g] + (uint32_t) mul_144[b]
bitmap[col + row * strike / 4] = (a << 24) + (bw << 16) + (bw << 8) + bw
 
設計一個 singly linked-list,對其作 bubble sort
Chun-I K
  • typedef struct ns {
  •     int value;
  •     struct ns *next;
  • } node;
...
759 days ago
Unfiled. Edited by Freeman Fang , 陳婉雅 759 days ago
p.62 hypervisor實例: 大核(CA15)/小核(CA7)之間互相切換(依功能需求切換另一個核心時會通知另一個核心開機並將當前核心關機), 但是切換過程中的interrupt (中間切換過程約需 200 us), 由誰來收 -> [sol] 在核心上增加一個 interrupt 處理單元
 
794 days ago
Unfiled. Edited by 陳婉雅 794 days ago
陳婉雅
  • [exam]:
  • (1) void swap (int *a, int *b) {
  • int t;
  • t = *a;
  • *a = *b;
  • *b = t;
  • }
  • 不用區域變數, 只用邏輯運算子實作swap
  • (a) 加減法
  • (b) bit-wise operator
Jim H
  • (2) quick sort 中的取中位數實做中,指出可能的正確性問題 (Hint: 邊界值)
陳婉雅
  • int的表示範圍: -2^31 ~ 2^31 -1
  • 兩個很大整數相加: 可能overflow
  •  
向澐
  • (3) 用 C 語言實做 char *reverse(char *s) 來反轉 NULL 結尾的字串,限定 in-place用遞迴
陳婉雅
  • 提示: 顯示的技巧
  • // abcd\0 => dcba\0
  • void reverse (char *s) {
  •   // base case
  •   if (*s == '\0') {
  •     printf ("%c", *--s); //刪掉, 偷偷執行過, 會多印, 變成"ddabc"
  •     return;
  •   }
  •   reverse (s+1);
  •   printf ("%c", *s);
  • }
  •  
  • int main (void) {
  •   char *s = "abcd";
  •   reverse (s);
  •   printf ("%c", '\0');    //結尾字元在外面印: 還算是遞迴嗎?
  • }
  • //結尾字元的解法: 參考同學solution: nested funtion
  • [Homework]:
 
Jim H
  • Find `char *mem = calloc(30000, 1);` in file `jit.dasc`
陳婉雅
  • got it!
 
 
char *mem = calloc(30000, 1);
fptr(mem);  //fptr : Function prologue開始的地方
edi : 1st argument to function call in x86 assembly abi
 
ARM : r0 - r3 as arguments
  • (3) 自己加上ARM assembly code, malloc tape ? 卡關中...
 
801 days ago
Unfiled. Edited by 陳婉雅 , Jim Huang 801 days ago
陳婉雅
  • 野人獻曝一下... x86架構的CPU動作summary:
  • system call from user level => trigger interrupt => 根據interrupt number, fetch the interrupt gate or trap-gate descriptor in IDT =>
  • 檢查CPL和DPL (current privilege level and descriptor privilege level), 決定是否entering lower privilege level(即進入kernel mode) => stack switch (根據預先設定好的task segment內容, load values to %ss and %esp) => save registers and set %cs and %eip (已進入kernel mode, 此時執行interrupt真正要作的事)
  • ARM架構的話, 我沒有研究過, 懇請補充~
  • 想看執行一行組語時, CPU到底做了哪些動作, 這邊再追加推坑IA32 vol2 ...無底洞阿
  • 還是涉及 CPU execution mode 的轉變,不過單純多了
 

Contact Support



Please check out our How-to Guide and FAQ first to see if your question is already answered! :)

If you have a feature request, please add it to this pad. Thanks!


Log in