# 晶心科技面試準備與心得

## 面試心得

> [name=紹華][time=Fri, Apr 7, 2017]

來信通知及聯絡我的面試主管叫做 greentime，約好了兩點到，可是因為 greentime 臨時有事，就變成其他主管來面試我，而且是五個依序進來面試(被轟得灰頭土臉)；第一個是所有組的主管(算是老闆吧)，主要是跟我聊聊天，觀察我的人格特質(他說的XD)。所以對自己的作品有把握的話，聊起天來就不會是大問題，而且他還很驚訝為什麼大學四年可以做這麼多東西。最後的我還有問待遇跟上班時間XD，對於實習生的待遇很不錯，都有三萬起跳，而且晶心的步調比較輕鬆(組長說的?)，基本上都是早九晚五，讓我很是喜歡晶心，至於他們喜不喜歡我又另當別論了Q_Q

---

後續的面試主管就都是組長等級的人來問問題，第二位組長先跟我介紹公司的 teamwork 跟環境，主要也是問大學計劃的事情，而且他對於我在 RTOS 的研究還蠻有興趣的，儘管我們是使用跟他們不同的架構(freeRTOS)。第二位組長並沒有問我一些面試題。

---
第三位組長是 compiler team 的，所以就對我做 comilper 助教這件事情很有興趣，但其實學習到的深度還是有差的，在 compiler 課程裡我們設計的作業，並沒有要求實作出 scope 的概念，這點就可惜了，不然可以聊上一陣子或者被 challenge 到爆；而寒暄的聊完後，組長就抽出了一張神奇白紙，面試題來啦!!這位組長給的都是程式設計題。

* 第一題是字串反轉，這題我寫了一個很直觀的方法，就頭尾對調，可是魔鬼藏在細節裡，被 '\0' 擺了一道，還是組長提醒我的

* 第二題則是實作出 BST insert function，這挺順利就寫出來了，沒什麼問題。

---
第四位組長是我覺得最親切的組長，因為時間問題所以進來只小聊了一下，就馬上出題目了；他出的題目是我寫起來最有把握的，都是些 pointer 的操作跟印值、程式寫法的優劣判斷跟一題 preprocessor 的用法。寫了快十來題，腦袋快燒掉了，但幸好有在寫 code 所以不是什麼難題，幾乎都有答出來，挺順利的，而且稍微錯的題目，這位組長還會提示跟訂正，人超 nice 的。

太多題了，挑個兩題示意一下，基本上不難，pointer 的題目都是一個大題組，記不起來= ="

* 請問該程式碼有何問題？

#define ADD(a,b) a+b

int multiple(int a, int b, int c, int d) {

    a = ADD(a,b);
    b = ADD(c,d);
    
    return ADD(a,b) * ADD(c,d);
}

這題很簡單，算是秒解，要注意的就是 preprocessor 是字串抽換。

* 請問上下兩段判斷，何者較佳？

if('A' == a) {
    a++;
}

if(a == 'A') {
    a++;
}

正解是上方，這題主要是在考驗 coding style 的技巧，上面的寫法比較好的是因為當`==`很有可能因為人為疏失被誤植為`=`，上者的寫法就會在 compile 階段出錯，這是一種透過 compiler 做 debug 的技巧。

---
最後一位組長就是聯絡我的 greentime，進來後先把自己所帶的 team 介紹一下，跟實習生進來後會需要處理什麼事情，聽完祥和語氣的介紹後就開始電我啦，因為面對這位組長的問題，我回答的最不滿意，所以記住大部份的問題，回家後要把腦洞補起來= =
>
> * 小技巧：回答時要舉例(最好是用自己開發過的專案)，主管對於教科書上的知識絕對都比我們還熟，所以處了照本宣科外，要記得融入自己 style 的回答。
> 如果是 jserv 來回答，他就會說，你就做一個可以動的 OS 給他就好了。
> 聽完，淚如雨下。

* deadlock 是什麼? 解法是?(張晏誠跟Y.C.大大提醒可以寫的更好，在放上 check model)

直接舉例來說，A在等待B握有的資源釋放，B在等待C握有的資源釋放，C在等待A握有的資源釋放，這樣互相等待彼此的資源釋放時，便會導致整個系統卡住，也就是著名的"哲學家就餐問題"(Dining philosophers problem)。

其解法有很多種，像是預防deadlock產生的演算法或是找出死結並恢復它的演算法，但因為這些演算法通常需要系統提供額外的資訊跟額外的運算量來偵測及預防deadlock的發生(像是提供程式需要的總資源，並透過中立的機制判斷誰該去釋放資源。)。因此現行最多作業系統採用的方法就是無視死結，假裝這些問題從來不曾發生過，並讓程式開發者自己來處理這些問題。

* race condition 是什麼？ 解法是什麼?

race condition 最主要是在 thread 間的競爭資源問題，當兩個 threads 執行到有相依性的 code section 時，而沒照著開發者預期的順序去執行時，便會產生非預期的結果。

thread 1 執行到 a++; // a 一開始為 0
thread 2 執行到 if(a == 0)

那 thread 2 結果會是?

其解法可以透過 mutex 來鎖住程式的 critical section，使其他 thread 要動用此變數時 block 住，藉此來保護該段 critical section。

* 上面提到 mutex 後，便被加問：為什麼 mutex 不會被競爭?

因為 mutex 使用 test_and_set 來實作，透過指令(instruction)層級的 atomic operation 來確保 mutex 本身不會受到競爭。

lock 實作 (這是busy-waiting 的機制，所以不是mutex ，但使用的 atomic operation是一樣的)

volatile int lock = 0;

void Critical() {
    while (TestAndSet(&lock) == 1); 
    /*
    critical section
    */
    lock = 0; // 釋放 lock
}

* segmentation fault 是什麼? 系統怎麼偵測 segmentation fault?(老師補充，等自己充份了解後再來補，抱歉><)

當記憶體存取到超出程式可用的範圍時，或是去寫入 read-only 的記憶體區段，就會產生 segmentation fault 的錯誤。像是宣告 100 個 entry 的 array，你卻去讀取第 300 個，就可能超出記憶體範圍或者嘗試去讀取 NULL 的 pointer。

~~當程式讀取到超出範圍的記憶體時，在 Linux 中，MMU 會負責發出 SIGSEGV 的 exception，當程式收到此 exception 如果該程式沒有定義 exception handler 時，便會執行預設的行為將程式停止。~~

> ~~segmentation fault = access violation，是一種 fault，由 Memory protect HW 通知 OS 該程式在存取非法記憶體區段，如 改動 read-only section，或是存取非該程式區段。~~
> ~~由**MMU**監控：當把 virtual memory 轉成 physical，如果存取的 virtual 記憶體根本不存在無法轉成 phisical，發起 invalid page fault，如果存取的記憶體根本存在，但非法則是illegal access，再交由 OS 把segmentation fault訊號傳給該 process。~~
>
> ex: int a = \*NULL_pointer
> ex: char* string = "hello >wolrd";string[3]='A';[name=Ponsheng]

* priority inversion 是什麼? 解法是?

舉例，有三個高、中、低優先權的任務，而低優先權的任務握有高優先權任務所需要的資源；當低優先權的任務被中優先權的任務中斷後，此時高優先權的任務進來，就會發生高優先權等待低優先權釋放資源，而低優先權任務卻又在等待中優先權任務釋放資源的情況。

解法為 priority inheritance，就像字面上繼承的意思，當低度優先權所握有的資源被較高優先權的任務請求時，並使低度優先權的任務繼承其優先權，讓任務執行完釋放資源後，再度回到原有的優先權。

* interrupt v.s exception

interrupt 是由硬體或軟體所送出的訊號(signal)，要求 CPU 即時處理該事件，此時 CPU 會儲存當前狀態，並執行 interrupt，執行結束後便返回原本的狀態。

而 exception 也為 interrupt 的一種，但是由軟體產生的中斷，且只在特定情況下才被稱為 exception，像是程式無法掌控的狀況，如 division by zero, invalid memory access，所以 segmentation fault 也為 exception 的一種。

> Interrupt 是傳給 CPU 的 signal,可由硬體或是軟體產生，代表某事件是要即時處理，此時CPU 儲存當下狀態，去執行 Intrrupt handler（or ISR），結束後回復原本執行位址。
>
> Hardware Interrupt 由周邊硬體產生，為非同步中斷（會在指令執行中發生），發起 Hardware Interrupt 也叫 interrupt request (IRQ). 如鍵盤按鍵或是USB插入觸發。
>
> Software Interrupt 由**特別處理器狀況**或是**特殊CPU指令**產生，前者也稱 Exception; 為同步中斷，在指令執行的當下就發生
>
> Exception = trap = fault(通稱，每個系統定義不一),可視為軟體的 Interrupt，代表該程式無法掌控的情況，如 divide-by-zero;可能由 system process 或 User process 發起，發起後通常轉到 Kernel space 處理，例如：發起 context switch，monitor program，debugger，或是遇到breakpoint, division by zero, invalid memory access
>[name=Ponsheng]

* page table 是什麼?

將程式切割成連續且分散的單一記憶體區塊(page)，並將所有 page 的資訊儲存在

儲存如何將 virtual memory maping 到 physical memory 上的結構，可將原本連續的 vm 對應到很多 page，這些 page 可能坐落在 pm 中分散的地方，甚至是存在 disk中
Page fault有兩種：
invalid page fault，vm 根本不存在page table中，產生 segmentation fault.
page fault: page 不在 memory 中，需要從 disk swap 到 meory，並更新 page table.

---

## 小結論

晶心對實習生的面試並不難，基本上我是沒準備就來面試的(請不要學我Q—Q)，被電完之後才曉得，這些都是 jserv 上課強調的重點，面完就去找他懺悔；面試前請重溫 OS 跟計組的一些重要關鍵字，至於程式題就看各人平時造化，有持續的再練習 coding 技巧就不會成為問題。

而且我遇到的主管人都很好，很願意跟我分享公司的細節跟在面試過程中指導我，很慶幸第一次的面試是在晶心。

最後，希望自己可以上XD

---

## 面試準備

* [中文的讚讚](http://www.doc00.com/doc/100100g79)
* [中文的讚讚](https://github.com/gatieme/LDD-LinuxDeviceDrivers/tree/master/study/kernel/02-memory/03-initialize/03-memblock)
* [中文的讚讚](http://blog.jobbole.com/108139/)
* [Linux Kernel Development](http://perso.crans.org/segaud/Addison-Wesley%20Professional%20Linux%20Kernel%20Development%203rd.pdf) (對問題沒幫助)
* [arm64 booting doc](http://lxr.free-electrons.com/source/Documentation/arm64/booting.txt)
* [arm64 memblock init](https://chengyihe.wordpress.com/2015/12/16/kernel-arm64-memblock-initialisation/)
* [About memblock(中文)](http://blog.chinaunix.net/uid-20378444-id-3189700.html)

### Tracing `Linux/arch/arm64/mm/init.c`

* __ro_after_init

* Read-only after initial
* https://lwn.net/Articles/676145/
* https://lwn.net/Articles/690058/
### SWIOTLB
* Linux includes swiotlb which is a software implementation of the translation function of an IOMMU. Also known as "bounce buffers".
* Linux always uses swiotlb on IA64 systems which have no hardware IOMMU, and can use it on x86_64 when told to do so or when a system has too much memory and not enough IOMMU.
* As of release 3.0.0, Xen always uses a modified version of swiotlb in dom0, since swiotlb provides machine contiguous chunks of memory (required for DMA) unlike the rest of the kernel memory allocation APIs when running under Xen.
* Using swiotlb (or any other IOMMU) is completely transparent to the drivers – everything is implemented in the architecture's DMA mapping API implementation.

### Memblock

* [Use memblock interface instead of bootmem](https://lwn.net/Articles/576281/)

* [Linux inside about memblock](https://0xax.gitbooks.io/linux-insides/content/mm/linux-mm-1.html)

struct memblock {
         bool bottom_up;
         phys_addr_t current_limit;
         struct memblock_type memory; 
         struct memblock_type reserved;
#ifdef CONFIG_HAVE_MEMBLOCK_PHYS_MAP
         struct memblock_type physmem;
#endif
};

bottom_up
~ which allows allocating memory in bottom-up mode when it is true.

current_limit
~ This field describes the limit size of the memory block.

memory, reserved and physmem
~ The next three fields describe the type of the memory block. It can be: `reserved`, `memory` and `physical memory` if the `CONFIG_HAVE_MEMBLOCK_PHYS_MAP` configuration option is enabled.

struct memblock_type {
    unsigned long cnt;
    unsigned long max;
    phys_addr_t total_size;
    struct memblock_region *regions;
};

cnt
~ It describes the number of memory regions which are inside the current memory block

max
~ the size of all memory regions

total_size
~ the size of the allocated array of the memory regions and pointer to the array of the memblock_region structures.

struct memblock_region {
        phys_addr_t base;
        phys_addr_t size;
        unsigned long flags;
#ifdef CONFIG_HAVE_MEMBLOCK_NODE_MAP
        int nid;
#endif
};

flags can have the following values

enum {
    MEMBLOCK_NONE    = 0x0,    /* No special request */
    MEMBLOCK_HOTPLUG    = 0x1,    /* hotpluggable region */
    MEMBLOCK_MIRROR    = 0x2,    /* mirrored region */
    MEMBLOCK_NOMAP    = 0x4,    /* don't add to kernel direct mapping */
};

* 關係示意圖

+---------------------------+   +---------------------------+
|         memblock          |   |                           |
|  _______________________  |   |                           |
| |        memory         | |   |       Array of the        |
| |      memblock_type    |-|-->|      memblock_region      |
| |_______________________| |   |                           |
|                           |   +---------------------------+
|  _______________________  |   +---------------------------+
| |       reserved        | |   |                           |
| |      memblock_type    |-|-->|       Array of the        |
| |_______________________| |   |      memblock_region      |
|                           |   |                           |
+---------------------------+   +---------------------------+

---

### 開機流程

[The example for dts](http://unix.stackexchange.com/questions/37729/how-can-i-reserve-a-block-of-memory-from-the-linux-kernel)

start_kernel()
    -> setup_arch()
        -> setup_machine_fdt()
            -> early_init_dt_scan()

* early_init_dt_scan()
* This function reads basic system setting from device tree.

early_init_dt_scan()
    -> early_init_dt_verify()

* early_init_dt_verify()
* This function checks device tree validity and assigns DTB address to `initial_boot_params`.

early_init_dt_scan() 
    -> early_init_dt_scan_nodes()
        -> early_init_dt_scan_chosen()
        -> early_init_dt_scan_root()
        -> early_init_dt_scan_memory()

* early_init_dt_scan_chosen()
* to read `/chosen/bootargs` as kernel command line
* early_init_dt_scan_root()
* to read `/memory/#address-cells` as address-cells, and read `/memory/#size-cells` as size-cells.
* early_init_dt_scan_memory()
* to parse `/memory/reg` to get all DDRs. It then calls memblock_add() to add memblock for each DDR.

early_init_dt_scan_memory()
    -> early_init_dt_add_memory_arch()
        -> memblock_add()

* early_init_dt_scan_memory() reads memory/reg. It then calls memblock_add() for each memory.

reserve memory blocks for kernel text, kernel data, initrd, and page table
This happens at the start of arm64_memblock_init().

---

### 記憶體轉換

virtual to physical
physical to virtual

#define __pa(x)    __virt_to_phys((unsigned long)(x))
#define __va(x)    ((void *)__phys_to_virt((phys_addr_t)(x)))

`memblock_reserve` call `memblock_reserve_region(base, size, MAX_NUMNODES, 0);`

---