# Firmware Interview
contributed by <`kylekylehaha`>
## Output of C Program
- [Output of C Program](/zQyj6MfVQ_Ozq3LvlNhZbw)
> 裡面放了些自己在練習時寫錯的題型。
---
## C Program
### Struct, Union, Memory Alignment
**Struct**: 存在在 stack，用完就丟。且每一個變數都佔記憶體。
**Union**: 全部成員共用同一連續記憶體，且同一時間只能儲存一個成員的職。
E.g., `sizeof(union)` = 8 bytes， 若是 struct 則會是 9 bytes。
```cpp=
typedef union{
char a;
int b;
int c;
}Demo;
```
**Memory Alignment**
記憶體會以 4 bytes 做對齊。比如說，抓第0, 4, 8, 12，若資料本身大小不夠 4 bytes，則會用 padding 的方式補空白。
```cpp
int main(int argc, char *argv[]){
struct align_test {
char x; // 1 byte
int y; // 4 bytes
short int z; // 2 bytes
};
struct align_test test;
printf("test size is %d\n", sizeof(test));
printf("x size is %d\n", sizeof(test.x));
printf("y size is %d\n", sizeof(test.y));
printf("z size is %d\n", sizeof(test.z));
printf("address of test is %p\n", &test);
printf("address of x is %p\n", &test.x);
printf("address of y is %p\n", &test.y);
printf("address of z is %p\n", &test.z);
}
```
Output:
> test size is ==12==
> x size is 1
> y size is 4
> z size is 2
> address of test is 0xbfd450a8
> address of x is 0xbfd450a==8==
> address of y is 0xbfd450a==c==
> address of z is 0xbfd450a==0==
E.g.,
```cpp=
struct a {
int a; // 4 bytes
short b; // 2 bytes
int c; // 4 bytes
char d; // 1 byte
};
struct b {
int a; // 4 bytes
short b; // 2 bytes
char c; // 1 byte
int d; // 4 bytes
};
sizeof("%zu, %zu", sizeof(struct a), sizeof(struct b));
```
output
> 16 bytes, 12 bytes
---
### Bit Classic Operation
- Set / Unset / toggle bit
- set $n^{th}$ bit -> `x | (1 << n)`
- Toggle $n^{th}$ bit -> `x ^ (1 << n)`
- Unset $n^{th}$ bit -> `x & ~(1 << n)`
- Power of 2 Test
- `return !(x & (x - 1))`
- Least significant 1 bit (找最小位元 1)
- `return (x & -x)`
- Letter Case: 大小寫剛好相差 32，可透過 AND, OR, XOR 來做全部大寫、全部小寫和大小寫交換。
- A ~ Z: 65 ~ 90
- a ~ z: 97 ~ 122
- 全部大寫: `x && 32`
- 全部小寫: `x | 32`
- 大小寫交換: `x ^ 32`
- Swap
```cpp=
void swap(int *a, int *b) {
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
}
```
- Count bit 1
```cpp=
int count_bit_1(int n) {
int count = 0;
while(n){
if (n & 1) {
count++;
}
n >>= 1;
}
return count;
}
```
---
### static, extern
**Static**:
用 static 修飾的變數被儲存在靜態資料區,在 compile 時就會畫分空間。若未對其進行初始化,則系統默認初始化為 0,只會初始化一次。
**用途**:
1. **設置 variable 的存儲域(==修飾 local variable==)**: 表示該 local variable 的 lifetime 和整個程式一樣長,但是作用範圍只在該 function 裡面。
- A variable declared static within the body of a function maintains its value between function invocations.
- 在函數裡面的被宣告為static的變數會在==函數呼叫之間==維持它的數值
```cpp=
void tmp(){
static int x = 10;
int y = 20;
x++;
y++;
printf("x: %d, y: %d\n", x, y);
}
int main(){
tmp();
tmp();
}
```
Output:
> x: 11, y: 21
> x: 12, y: 21
2. **限制 variable 的作用域(==修飾 global variable==)**: You should not define global variables in header files. You should define them in .c source file.
- If global variable is to be visible within only one .c file, you should declare it `static`.
- If global variable is to be used across multiple .c files, you should not declare it static. Instead you should declare it `extern` in header file included by all .c files that need it.
> 用 static 修飾 global variable，讓該 variable 只會被該 .c file 給看到。
**E.g.,**
**example.h**
```cpp=
extern int global_foo;
void foo_func(void);
void bar_func(void);
```
**foo.c**
```cpp=
# include <stdio.h>
# include "example.h"
int global_foo = 100; // 必須宣告在 .c file
static int local_foo = 10; //
void foo(){
/* sees: global_foo and local_foo
cannot see: local_bar */
printf("foo(): global_foo: %d, local_foo: %d\n", global_foo, local_foo);
global_foo++;
}
```
**bar.c**
```cpp=
# include <stdio.h>
# include "example.h"
static int local_bar = 50;
static int local_foo = 200;
void bar_func(){
/* sees: global_foo, local_bar */
/* sees also local_foo, but it's not the same local_foo as in foo.c
it's another variable which happen to have the same name.
this function cannot access local_foo defined in foo.c
*/
foo();
printf("bar(): global_foo: %d, local_bar: %d, local_foo: %d\n", global_foo, local_bar, local_foo);
}
```
**main.c**
```cpp=
# include <stdio.h>
# include <example.h>
int main(){
foo_func();
bar_func();
}
```
output:
> foo(): global_foo: 100, local_foo = 10
> bar(): global_foo: 101, local_bar: 50, local_foo = 200
p.s. how to compile?
> gcc main.c foo.c bar.c -o main
3. 修飾 function: 和修飾 global variable 一樣。
---
### volatile, inline
**Volatile**
說法一：(I/O, multithread 較常用):
volatile 修飾的變數,compiler 就對該變數進行存取時都會「立即更新」,不會對其做任何最佳化,
並在每次操作它的時候都去讀取該變數 memory 上最新的值,而不是讀取 cache 上的值,一般的
變數可能因為剛剛讀取過而放在 CPU 暫存器上使動作變快。
- 使用方式 : (1) 硬體暫存器,如狀態暫存器 (2)多執行緒所共用的全域變數。
說法二:
==一個被定義為volatile的變數代表說這個變數會不可預期的被改變。因此，編譯器就不會去假設這個變數的值了==。具體來說，編譯器在用到這個變數時，每次都會小心地重載這個變數，而不是使用保存在暫存器的備份。Volatile變數的範例如下:
- ( a ) 周邊設備的硬體暫存器，如狀態暫存器
- ( b ) 中斷服務函式(ISR)中會訪問到的非自動變數(Non-automatic variables)
- ( c ) 多執行緒應用中，被多個任務共享的變數
例子：
- 並行設備的硬體暫存器 (如︰狀態暫存器)
- ISR會修改的全域變數或static變數
- 多執行緒下被多個task共享的變
:::success
- volatile英文意思是可變的。在C語言中，一個定義為volatile 的變數是說這變數很可能會被意想不到地改變，因此需要小心對待。
- 也就是說，優化器在用到這個變數時必須每次重新從虛擬記憶體中讀取這個變數的值，而不是使用儲存在暫存器裡的備份。
:::
**inline**
(不熟)
---
### const
**用途:** 可以修飾函數的參數、返回值,甚至函數的定義體。==被 const 修飾的東西都受到強制保護,可以預防意外的變動==，能提高程序的健壯性。
==使用 const 定義變量時,一定要進行初始化==。
- 在 `*`, `&` 左邊是修飾指向的內容
- 在右邊是修飾本身。
**E.g.,**
- a) `const int *p1`: `p1` 可修改(可指向不同的數據)，但指向的數據不可修改。
- b) `int const *p2`: `p2` 可修改(可指向不同的數據)，但指向的數據不可修改。
- c) `int * const p3`: `p3` 只可讀，不可修改(因為在 `*` 的右邊，修飾本身)，但指向的數據可以修改。
- d) `const int * const p4`: `p4` 不可修改，且指向的數據不可修改。
- e) `void func(const int a)`: 函數內不可修改該參數。
- f) `const int func()`: 函數的返回值不可被修改。
---
### Pointer 判讀
- `int a`: An integer.
- `int *a`: A pointer to an integer.
- `int **a`: A pointer to a pointer to an integer.
> 為何要用 pointer to pointer? 取值取址 改變資料結構需要 get 地址
- `int a[10]`: An array of 10 integers.
- `int *a[10]`: An array of 10 pointers to integers.
- `int (*a)[10]`: A pointer to an array of 10 integers.
- `int (*a)(int)`: A pointer to a function that takes an integer argument and returns an integer.
- `int (*a[10])(int)`: An array of 10 pointers to functions that take an integer argument and return an integer.
---
### Void
- function(void): 表示 function 不接受任何輸入。
- function(void* a): 表示 function 的輸入可以是任何的 pointer。
---
### Lvalue & Rvalue
- Lvalue : 經過運算式後還保留其狀態的一個物件。==所有的 variables 包含 const 的變數都是 Lvalue。==
- Rvalue: 就是==一個運算式過後其狀態就不會被保留了==,也就是一個暫存的數值。
> 另一種說法(不完全正確, 但是可以依此來稍做判斷) 能出現在 assignment 運算子(=)的左邊的稱為 Lvalue,而只能出現在右邊的稱為 Rvalue。
---
### interrupt
下列程式碼，有三個錯，請找出：
```cpp=
__interrupt double compute_area(double radius) {
double area = PI * radius * radius;
printf(“nArea = %f”, area);
return area;
}
```
- a) ==Interrupt service routines cannot return a value.==
- b) ==ISR’s cannot be passed parameters.==
- c) On many processors / compilers, floating point operations are not necessarily re-entrant. In some cases one needs to stack additional registers, in other cases, one simply cannot do floating point in an ISR. Furthermore, given that a general rule of thumb is that ISRs should be short and sweet, one wonders about the wisdom of doing floating point math here.
- c) 在許多編譯器/處理器中，浮點數操作是不可重入的(re-entrant)。有些處理器/編譯器需要讓多餘的暫存器入棧(PUSH入堆疊)，有些處理器/編譯器就是不允許在ISR中做浮點運算。此外，==ISR應該是短而有效率的，在ISR中做浮點運算是不明智的。==
Reference: [工程師應知道的0x10個問題(11): 中斷](https://medium.com/@racktar7743/工程師應知道的0x10個問題-11-中斷-7c59ac7a10c4)
---
### Big Endian & Little Endian:
```cpp=
#include <stdio.h>
int main() {
char data[8] = {1, 2, 3, 4, 5, 6, 7, 8};
short *a = (short*)&data[0];
int b = *a;
printf("%d", b);
return 0;
}
```
重點在第二行: `short *a = (short*)&data[0]`
- Casts the address of the first element of the data array to a pointer to short.
- This allows interpreting the first two bytes of the char array as a short.
The actual output depends on the system's endianness.
- Little-endian systems: The least significant byte is stored first. ==Therefore, the bytes {1, 2} in the char array would be interpreted as the short value 0x0201. = 513==
- Big-endian systems: The most significant byte is stored first. ==Therefore, the bytes {1, 2} in the char array would be interpreted as the short value 0x0102 = 258==
**Summary**
The program interprets the first two bytes of the char array as a short and prints it as an int. The output depends on the system's endianness, with common little-endian systems resulting in 513.
**How to know computer is big endian or little endian?**
```cpp=
#include <stdio.h>
int main() {
unsigned int x = 1;
char *c = (char*)&x;
if (*c)
printf("Little Endian\n");
else
printf("Big Endian\n");
return 0;
}
```
- 
## Operating System
### Process VS. Threads
- Process 是 ==OS 分配 resource 的單位==，相對的 Thread 是 ==OS 分配 CPU-time 的單位==。
- Process 之間的溝通相對複雜，要嘛是跟 OS 要一塊 Shared Memory，不然就是透過 OS Message passing，而 Thread 之間的溝通相對簡單，只要透過 Global Variable 即可，雖然可能會有些問題（Race Condition）不過整體是比較簡單的。
---
### CPU Scheduling
- 常見的 CPU Scheduling: First in first out / Priority / Shortest First / Round robin(RR)
- CPU Scheduling Criteria:
- CPU utilization : 讓 CPU 盡量保持忙碌。
- Throughput : 在單位時間之內能夠完成的工作量。
- Turnaround time : 對每一個 process,從他進入到完成所需要花費的時間。
- Waiting time : process 在完成之前，待在 waiting queue 裡的時間。
- Response time : 當 process 進來時，最快花多少時間可以被選到。
---
### Critical Section
Critical Section 是在 multithreading 中受保護的程式區段,==保護 CS 目前執行的 thread/process 不被其他 thread/process 影響==,提供對共享變數之存取的互斥控制,從而確保資料正確。
控制 critical section 執行之機制必須滿足下列三個要求:
1. mutual exclusion (互斥) : 不允許兩個以上的 process 同時在對應的 CS 中執行。
2. progress (要有進度不能卡住): 不想進入 CS 的 thread 不可以阻礙其它 thread 進入 CS,即不可參與進入 critical section 的決策過程。
3. bounded waiting (不能一直無限等): 控制機制必須使等待進入 CS 之 process 在有限時間內進入 critical section。
---
### Race Condition
若多個 process 使用 share variables 溝通，若未對這些共享變數之 read, write 提供任何 synchronization，==使得共享變數之最終值，會因 process 之間交錯執行順序不同，而有不同的結果。==
E.g., Pi 執行 `c = c + 1`, Pj 執行 `c = c - 1`， `c` 初值為 5
- `c = c + 1` 的 assembly language:
```
R1 = c // line 1
R1 = R1 + 1 // line 2
c = r1 // line 3
```
- `c = c - 1` 的 assembly language:
```
R2 = c // line 4
R2 = R2 - 1 // line 5
c = R2 // line 6
```
若按照 1, 2, 4, 5, 3, 6 的順序，則 c = 4
若按照 1, 2, 4, 5, 6, 3 的順序，則 c = 6
若按照 1, 2, 3, 4, 5, 6 的順序，則 c = 5
---
### Mutex & Semaphore
==最大的差異在於 Mutex 只能由上鎖的 thread 解鎖，而 Semaphore 沒有這個限制，可以由原本的 thread 或是另外一個 thread 解開==。另外，Mutex 只能讓一個 thread 進入 critical section，Semaphore 的話則可以設定要讓幾個 thread 進入。這讓實際上使用 Mutex 跟 Semaphore 場景有很大的差別。 [更詳細的回答](https://blog.louie.lu/2016/10/22/mutex-semaphore-the-difference-and-linux-kernel/)
**E.g.,**
Linux 和 MacOS 會有些許不同（本人在 MacOS 上實作)
在 OS X 上最大不同，必須用 `sem_open()` 來代替 `sem_init()`
- `sem_open(const char *, int oflag, mode_t mode, unsigned int value)`
- [sem_open](https://man7.org/linux/man-pages/man3/sem_open.3.html)
- `O_CREAT` , `O_EXCL`: If both `O_CREAT` and `O_EXCL` are specified in oflag, then an error is returned if a semaphore with the given name already exists.
- [mode_t mode](https://man7.org/linux/man-pages/man2/open.2.html)
- S_IRWXU 00700 user (file owner) has read, write, and execute permission
- S_IRUSR 00400 user has read permission
- S_IWUSR 00200 user has write permission
- S_IXUSR 00100 user has execute permission
- `value`: semaphore initialization value
```cpp=
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <semaphore.h>
//sem_t semaphore; // Use on Linux
sem_t *sem; // Use on OS X
int counter = 0;
// 子執行緒函數
void* child() {
for(int i = 0;i < 5;++i) {
// sem_wait(&semaphore); // Use on Linux
int ret = sem_wait(sem); // Use on OS X
if (ret != 0) {
perror("sem_wait failed");
}
printf("Counter = %d\n", ++counter);
sleep(1);
}
pthread_exit(NULL);
}
// 主程式
int main(void) {
// 初始化旗標，僅用於本行程，初始值為 0
// sem_init(&semaphore, 0, 0); // Use on Linux
/* Mac 沒有 sem_init，只有 sem_open */
/* sem_open("semaphore的名字(自己取)", O_CREATE | O_EXCL, thread 對這個 semaphore 的權限(Only read or only write), semaphore value)*/
sem_unlink("sem_test"); // 怕之前有人創建 semaphore 後忘了刪除
sem = sem_open("sem_test", O_CREAT|O_EXCL, S_IRWXU, 0);
// 若創建 semaphore 失敗，則會回傳 SEM_FAILED
if (sem == SEM_FAILED) {
perror("sem_open failed");
return -1;
}
pthread_t t;
pthread_create(&t, NULL, child, NULL);
// 送出兩個工作
printf("Post 2 jobs.\n");
// sem_post(&semaphore);
// sem_post(&semaphore);
sem_post(sem);
sem_post(sem);
sleep(4);
// 送出三個工作
printf("Post 3 jobs.\n");
// sem_post(&semaphore);
// sem_post(&semaphore);
// sem_post(&semaphore);
sem_post(sem);
sem_post(sem);
sem_post(sem);
pthread_join(t, NULL);
return 0;
}
```
output
> Post 2 jobs.
> Counter = 1
> Counter = 2
> Post 3 jobs.
> Counter = 3
> Counter = 4
> Counter = 5
---
### Deadlock
4 個條件都滿足就會造成 Deadlock,解決其一即可:
- (1) Mutual exclusion :資源同時給兩個人用
- (2) Hold and Wait :拿了份資源,還想拿別人的資源。process 必須保證一個行程在要求一項資源時,不可以佔用任何其它的資源。
- (3) No preemption :占用資源很久但還不能剝奪他的資源。只要某個 process 要不到所要求的資源時,就要把它已經擁有的資源釋放,再重新要求。
- (4) Circular wait : A 等 B,B 等 C,C 又等 A,大家都在互等。確保循環式等候的條件不成立,我們對所有的資源型式強迫安排一個線性的順序。
---
### Context Switch
程式在執行時會從 memory 中讀取指令和依照指令做計算並由 core registers (CPU 內部的 register) 來紀錄讀取到哪裡了,以及當作計算時的暫存區域。CPU 在執行時,只能運用一個 process,如果切換給另一個 Process 時,須將舊 Process 的內容進度儲存在 memory,並載入新 Process 的相關資訊。
---
### RISC vs. CISC
- Reduced / Complex Instruction Set Computer(指令集架構)。原本的架構都是龐大的指令集，其中 20% 比較常用所以包成 reduced。
## Computer Architecture
### Interrupt & ISR & Exception
Kernel 所在的 memory area ，會存 Interrupt vector，裡面存放各式 interrupt ID 和 ISR 位址，並存放 **Interrupt Service Routine (ISR)** 的 Binary code.
Interrupt 發生後，OS 處理的 steps
1. OS 收到中斷後，若要立即處理，則會暫停目前 process 執行，且保存其 status。
2. OS 會查詢 interrupt vector, based on interrupt ID，找到對應的 ISR 位址
3. Jump to ISR 位址，執行 ISR
4. 待 ISR 完成後，return control to kernel
5. kernel 恢復中斷錢的 process 執行
**Exception & Interrupt**
For MIPS, using the term **exception** to refer *any* unexpected change in control flow without distinguishing whether the cause is internal or external.
| Type of element | From where?| MIPS terminology |
| -------- | -------- | -------- |
| I/O device request| external | interrupt |
| Invoke the OS from user program | internal | exception |
| Arithmetic overflow | internal |exception |
| Using an undefined instruction | internal | exception |
==Interrupt 實作== (Undone)
---
### DMA
一種 IC,task 取用 memory 中的資料不需透過 CPU & controller,可直接存取。優點是加快資料讀寫時間。
---
### Hazard
---
### Memory
## Reference
- [Data Structure Alignment](https://kezeodsnx.pixnet.net/blog/post/27585076)
- [bit - 演算法筆記](https://web.ntnu.edu.tw/~algo/Bit.html)
- [c - When to use static keyword before global variables?](https://stackoverflow.com/questions/1856599/when-to-use-static-keyword-before-global-variables)
- [Compiling multiple C files in a program](https://stackoverflow.com/questions/8728728/compiling-multiple-c-files-in-a-program)
- [韌體工程師的0x10個問題](https://hackmd.io/@Chienyu/S1loEqCuo)
Sign in with Wallet
Connect another wallet