筆記

Command Substitution

Command substitution allows the output of a command to replace the command itself in a shell script or command line.

1. `command`
2. $(command)

Example:

echo "Today is $(date)"
echo "Nested: $(echo $(date))"

如果需要巢狀的情況，用 ` 會混淆，用 $() 會比較好

---

常用符號

• -: dash, minus
• +: plus, sign
• _: underscore
• `: backtick 或 backquote
• ': single quote
• ": double quote
• {: curly brace 或 brace
• [: square bracket 或 bracket
• (: parenthesis 或 round bracket
• !: exclamation mark, NOT, reverse
• ~: tilde, bitwise not
• ?: question mark
• :: colon
• #: hash 或 pound
• &: ampersand
• ^: caret, XOR
• *: asterisk 或 star
• =: assign
• ==: comparison
• /: slash
• \: backslash

---

apt 跟 apt-get 的差別

sources:

1. What’s the Difference Between APT and APT-GET?

Similarity

• Debian-based Linux operating systems use the Advanced Package Tool (APT) to manage Linux software packages.
• Both apt and apt-get are command line tools. You can use them to manage software packages like applications and libraries on Debian-based Linux servers and server instances.
• apt-get and apt are the system default.

Main difference

• The apt command line tool provides a higher-level user interface for end users with intuitive commands, resulting behaviors, and security features. In contrast, the command apt-get is a low-level interface that communicates more closely with core Linux processes.
• The apt command is a more user-friendly package manager than apt-get.

Release dates

In 1998, apt-get was released with the Debian 2.0 (Hamm) distribution, while apt was released in 2014 with the Debian 8 (Jessie) distribution. After 2014, apt replaced apt-get as the default package manager tool for all Debian-based Linux distros.

Search capabilities

Search for a package by name by using the apt search <package_name> command. This command gives a detailed description of all packages containing the searched package_name. This operation was not possible with apt-get. Instead you had to use the apt-cache command.

Dependency resolution

Any software package typically comes with a list of software dependencies, such as libraries or tools it needs to operate correctly. You have to install all dependencies before you can install the package.

Both apt and apt-get handle dependency resolution, however apt is far superior. It determines complex dependency chains where it installs packages in the correct order and recommends suggested packages to install.

Package versions on the file system

By default, the apt upgrade command removes old versions of installed or upgradeable packages on the system that are no longer needed when upgrading. In contrast, the apt-get upgrade command does not. This efficiency can make apt upgrade better for freeing up system memory.

Printed outputs to the terminal

Both apt-get and apt print status information to the terminal, giving insight into what the system is doing after the input command. The apt command provides slightly more detailed information to the user, including a progress bar on each task.

某些命令，像是 search, show, policy，apt-get 必須搭配 apt-cache 才能使用，而在 apt 中可以直接使用

可以說 apt 是 apt-get 的進階版工具

---

Makefile

太久沒用每次都不知道怎麼寫

sources:

1. Docker with Makefile
2. Makefile Introduction
3. GNU: The C Preprocessor
4. Makefile Header File Dependency

• % : wildcard pattern
• := : append assignment
• ?= : assignment operator; if not define, then define it
• dir : 取得檔案的 directory
• wildcard
• patsubst : $(patsubst %.c, %.o, <SRC>)
• addprefix
• addsuffix
• $@ : target files
• $^, $|, $~, $+, `` : all dependencies / prerequisite
• $? : all dependencies newer than target
• $< : first dependency / prerequisite
• $* : stem of target
• $% : target member name
• ifeq (), ifneq (), endif
• $(warning) , $(error)
• $(shell <command>)

Templates

只給基本範例，如果有多個 header files 或是其他 libraries 要一起編譯，再自己查資料

# C

CC = gcc
CC := $(CC) -std=c99
CFLAGS = -Wall -Wextra -O2 -g

SRC = $(wildcard *.c)
OBJ = $(SRC:.c=.o)
OUT = a.out

# phony targets; indicate some targets that are not files
.PHONY: all clean

all: $(OUT)

$(OUT): $(OBJ)
	$(CC) $(CFLAGS) -o $@ $^

$(OBJ): $(SRC)
	$(CC) $(CFLAGS) -c -o $@ $<

clean:
	rm -f $(OBJ) $(OUT)

# CPP

CC = g++
CC := $(CC) -std=c++11
CFLAGS = -Wall -g -O2

SRC = $(wildcard *.cc)
OBJ = $(SRC:.cc=.o)
OUT = a.out

.PHONY: all clean

all: $(OUT)

$(OUT): $(OBJ)
	$(CC) $(CFLAGS) -o $@ $^

%.o: %.cc
	$(CC) $(CFLAGS) -c -o $@ $<

clean:
	rm -f $(OBJ) $(OUT)

Flags 的意義

sources:

1. 常用 flags 解釋

-MMD

See references:

1. Using-mmd-in-Makefile Stackoverflow

• The dependency information is only needed when .o files are already present, and you've changed a .h file. The first time you run Make, all .o files will need to be built anyway, and the .d files are generated at the same time.
• After that, the .d files will give dependency information. If a header is changed, the dependency information will tell Make which .o files need rebuilding. If a source file is changed, the .o will always need to be rebuilt, and updated dependency information will be generated at the same time.

-

• 告訴 makefile 忽略失敗

-std=<standard>

• Specify the language standard to compile for.
• -ansi: Same as -std=c89

See references:

1. Options Controlling C Dialect
2. Language Standards Supported by GCC

可以 man clang 或 man gcc 來看

Supported values for the C language are:
    c89
    c90
    iso9899:1990

        ISO C 1990
    iso9899:199409

        ISO C 1990 with amendment 1
    gnu89
    gnu90

        ISO C 1990 with GNU extensions
    c99
    iso9899:1999

        ISO C 1999
    gnu99

        ISO C 1999 with GNU extensions
    c11
    iso9899:2011

        ISO C 2011
    gnu11

        ISO C 2011 with GNU extensions
    c17
    iso9899:2017

        ISO C 2017
    gnu17

        ISO C 2017 with GNU extensions

  The default C language standard is gnu17, except on PS4, where
  it is gnu99.

Supported values for the C++ language are:
    c++98
    c++03

        ISO C++ 1998 with amendments
    gnu++98
    gnu++03

        ISO C++ 1998 with amendments and GNU extensions
    c++11

        ISO C++ 2011 with amendments
    gnu++11

        ISO C++ 2011 with amendments and GNU extensions
    c++14

        ISO C++ 2014 with amendments
    gnu++14

        ISO C++ 2014 with amendments and GNU extensions
    c++17

        ISO C++ 2017 with amendments
    gnu++17

        ISO C++ 2017 with amendments and GNU extensions
    c++20

        ISO C++ 2020 with amendments
    gnu++20

        ISO C++ 2020 with amendments and GNU extensions
    c++23

        ISO C++ 2023 with amendments
    gnu++23

        ISO C++ 2023 with amendments and GNU extensions
    c++2c

        Working draft for C++2c
    gnu++2c

        Working draft for C++2c with GNU extensions

  The default C++ language standard is gnu++98.

-Wall

• 開啟「大部分」的 warning，主要目的是處理一些雖然可以順利編譯，但可能會對結果有影響的問題。這個 flag 有點像總開關，開啟 -Wall 時，其實是在背後幫你開啟更多其他相關 flag。雖然這裡的用字是 "all"，但實際上它沒有開啟所有 warning 相關的 flag

-Wextra

• 除了 -Wall 開啟的 warning 以外，額外再多開啟一些

-w (小寫 w)

• 忽略所有 warning

-Werror

• 將 warning 視為 error

-Werror=switch

• 將特定的 warning 視為 error

-Wfatal-errors

• 編譯的時候，遇到第一個 error 時就中止編譯
• 錯誤訊息很多的時候看了很煩，用這個就可以讓錯誤訊息少一點，一次解決一個

-Wformat-security

• 其實我也不太確定這個在幹嘛，只知道它會檢查可能的 unsafe format string

-Wfloat-equal

• 檢查有沒有對浮點數做 a == b 這種比較

-Wdiv-by-zero

• 檢查有沒有除法的分母是 0

-Wshadow

• 當發生 variable shadowing （inner scope 內的變數跟 outer scope 的變數有同樣的名字，也就是 outer scope 的變數被 "shadowed"）時發出 warning

-Wmissing-prototypes

• 沒有定義 function prototype 時呼叫該 function，會跳一個 warning

-O2

• 開啟 level 2 的最佳化編譯，可以提升執行速度。它跟 -Wall 很像，都是總開關類型的，也就是開啟 -O2 時其實是在背後幫你開更多 optimization flag
• -O2 包含了大多數的 optimization flag，不過有一些例外，像是 -ffast-math（因為這可能會導致結果有誤差）或是 -funroll-loops（因為這會讓執行檔案大小變大很多，但卻不保證能夠加速編譯速度）
• -O3 ： 開啟 level 3 的最佳化編譯，通常會比 -O2 再快一點（編譯速度）
• -O3 不保證一定會比 -O2 更快（編譯速度）

-ffast-math

• 用來大幅提高浮點運算的速度
• 透過違反 IEEE 標準、將 code 轉換成在數學上等效（但在浮點數運算上可能不等效）的形式
• 舉例來說，寫 a*a*a*a*a*a 時，一般情況下 compiler 不會做什麼處理，就是連續做 5 次乘法，但是開啟 -ffast-math 時，compiler 會把它重新變成 (a*a*a)*(a*a*a)，這樣只需要做 3 次乘法，速度就比較快，但也導致結果可能有準確性的問題

-funroll-loops

• 把某些迴圈展開來
• 「某些」迴圈指的是迭代次數能夠在編譯 or 進入迴圈前確定，如果沒辦法的話則迴圈不會被展開
• 可以透過 -funroll-all-loops 來強制展開所有迴圈，但開啟這個很有可能反而減慢速度
• -funroll-loops 不保證一定會加快（執行）速度

-march=native

• 根據 cpu 的指令集架構，編譯成適合目標系統處理器架構的程式碼，或是優化方式
• 如果目標處理器支援特定的指令集（像是 AVX、SSE 等），並且 source code 已經為這些指令集做好準備，編譯器會生成相應的指令來達到最佳效能。

This tells the compiler what code it should produce for the system's processor architecture (or arch); it tells GCC that it should produce code for a certain kind of CPU. Different CPUs have different capabilities, support different instruction sets, and have different ways of executing code. The -march flag will instruct the compiler to produce specific code for the system's CPU, with all its capabilities, features, instruction sets, quirks, and so on provided the source code is prepared to use them. For instance, to take benefit from AVX instructions, the source code needs to be adapted to support it.

---

Storage duration (變數儲存週期)

Static Storage Duration (靜態儲存週期)

• 在函式外的全域變數或在函式內但是刻意以 static 關鍵字修飾的變數會是屬於 static storage duration
• 他的生命週期 (lifetime) 是從程式開始執行的時候開始，程式結束之後才會被釋放
• 整個程式運行時會佔用固定的記憶體空間

int g_variable1;     /* Static Storage Duration */
int g_variable2 = 5; /* Static Storage Duration */
int g_array[10];     /* Static Storage Duration */

int main() {
    static int local_static_variable; /* Static Storage Duration */
    return EXIT_SUCCESS;
}

Static storage duration 的變數會有以下特性：

1. 如果宣告時有被初始化，其值會等於初始值
2. 如果宣告時沒有被初始化，且其型別為算術型別 (arithmetic type)，其值會被初始化為零
3. 如果宣告時沒有被初始化，且其型別為指標型別，其值會被初始化為 NULL

g_variable1 = 0
local_static_variable = 0
g_variable2 = 5
a = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

Automatic Storage Duration (自動儲存週期)

• 在函式內部的變數、函式的引數 (argument) 如果沒有特別聲明，就是 automatic storage duration
• 變數的生命週期始於存放變數的視野 (scope) 開始處，止於視野的結束處

int main() {
    int variable1;     /* Automatic Storage Duration */
    int variable2 = 0; /* Automatic Storage Duration */

    int array1[4];                /* Automatic Storage Duration */
    int array2[4] = {1, 2, 3, 4}; /* Automatic Storage Duration */
    int array3[4] = {1, 2};       /* Automatic Storage Duration */

    {
        int i; /* Automatic Storage Duration */
    }
    /* Now, "i" is dead */

    return EXIT_SUCCESS;
}
/* Now, "variable1", "variable2", "array1", "array2" is dead. */

Automatic storage duration 的變數會有以下特性：

1. 生命週期開始於宣告處，終止於所在的視野結束時
2. 每一次函式呼叫都會配置獨立的記憶體區塊
3. 除非有指明，不然所有的變數不會被初始化
4. 第三點的例外為陣列的元素如果有一個有初始值，則所有的元素都會有初始值
   • 此時沒有指定初指值的變數會以 static storage duration 的方法初使化

根據第4點

array3 = { 1, 2, 0, 0 }

有時候我們會在宣告的後面加上 int a[3] = {0} 來將整個陣列初始化為 0
不過要注意的是 int a[3] = {10} 並非把所有的元素初始化為 10，只有第一個會是 10，其他的都會是 0。

Heap Storage Duration (堆積儲存週期)

• heap storage duration 是用於動態配置記憶體
• 其生命週期是在被 malloc 時開始，結束於 free 的時候
• heap storage duration 不會被初始化

int main() {
    int *my_array = (int *)malloc(sizeof(int) * 10);
    free(my_array);

    return EXIT_SUCCESS;
}

需要注意的是 my_array 這一個指標本身是屬於 automatic storage duration，是may_array 所指向的變數才是 heap storage duration。

Magic Number (Hexspeak)

0xDEADBEEF

• dead beef 在嵌入式系統中常用於標示軟體崩潰或是死結，在 IBM RS/6000 系統、32 位 PowerPC 處理器上的 Mac OS 系統以及 Commodore International 的Amiga 電腦上都有使用
• 而在 Sun 的 Solaris 作業系統中，這一魔術數則用於標記已釋放的記憶體儲存空間
• 另外，在 Alpha 處理器上的 OpenVMS 作業系統中，按下 CTRL+T 就可以看到DEAD_BEEF
• DEC Alpha 的存儲資源管理控制台亦有一個用於檢測記憶體錯誤的後台進程，PS 識別為「BeefEater waiting on 0xdeadbeef」

整型提升 (Integral Promotion)

sources:

1. 整型提升-wiki

A character, a short integer, or an integer bit-field, all either signed or not, or an object of enumeration type, may be used in an expression wherever an integer maybe used. If an int can represent all the values of the original type, then the value is converted to int; otherwise the value is converted to unsigned int. This process is called integral promotion.

• 表達式的整型運算要在 CPU 的相應運算器件內執行，CPU 內整型運算器（ALU）的操作數的字節長度一般就是 int 的字節長度，同時也是 CPU 的 general purpose register 的長度
• 因此，即使兩個 char 類型的相加，在 CPU 執行時實際上也要先轉換為 CPU 內整型操作數的標準長度
• 一般的 CPU 難以實現兩個 8-bit char 直接相加運算，所以表達式中各種長度可能小於 int 長度的整型值，都必須先轉換為 int 或 unsigned int，然後才能送入 CPU 去執行運算

C 語言中規定

sizeof(char) ≤ sizeof(short) ≤ sizeof(int)

1. 這意味著 short int 與 int 的長度相等的可能
2. 這種情形下，unsigned short 就無法提升為 int 表示，只能提升為 unsigned int

char a = 0xb6;
short b = 0xb600;
int c = 0xb6000000;

if (a == 0xb6);        // false
if (b == 0xb600);      // false
if (c == 0xb6000000);  // true

unsigned int + signed int 會被 promoted 成 unsigned

unsigned int a = 6;
int b = -20;
(a + b > 6) ? puts("big") : puts("small");

// output: big

String Initialization

sources:

1. Why do I get a segmentation fault when writing to a "char *s" initialized with a string literal, but not "char s[]"?

char a[] = "string literal";
char *p  = "string literal";

A string literal (the formal term for a double-quoted string in C source) can be used in two slightly different ways:

1. As the initializer for an array of char, as in the declaration of char a[] , it specifies the initial values of the characters in that array (and, if necessary, its size).
2. Anywhere else, it turns into an unnamed, static array of characters, and this unnamed array may be stored in read-only memory, and which therefore cannot necessarily be modified. In an expression context, the array is converted at once to a pointer, as usual (see section 6), so the second declaration initializes p to point to the unnamed array's first element.

Some compilers have a switch controlling whether string literals are writable or not (for compiling old code), and some may have options to cause string literals to be formally treated as arrays of const char (for better error catching).

NULL pointers and \0

sources:

1. What is the difference between NULL, '\0' and 0?
2. Should I use NULL or 0?
3. Is NULL always zero in C
4. What's the difference between null pointers and NULL?
5. Is the abbreviated pointer comparison if(p) to test for non-null pointers valid? What if the internal representation for null pointers is nonzero?
6. Null Pointers

null pointers and null pointer constants are formally defined in C17 6.3.2.3/3:

An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant. If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.

The macro NULL is defined in <stddef.h> (and other headers) as a null pointer constant

NULL which expands to an implementation-defined null pointer constant

Null Pointers

If a pointer is being compared to the constant literal 0, then this is a check to see if the pointer is a null pointer. This 0 is then referred to as a null pointer constant. The C standard defines that 0 cast to the type void * is both a null pointer and a null pointer constant.

Here are some valid ways to check for a null pointer:

if (pointer == NULL)   // valid

NULL is defined to compare equal to a null pointer. It is implementation defined what the actual definition of NULL is, as long as it is a valid null pointer constant.

if (pointer == 0)      // valid

0 is another representation of the null pointer constant.

if (!pointer)          // valid

This if statement implicitly checks "is not 0", so we reverse that to mean "is 0".

int mynull = 0;
// some code here
if (pointer == mynull) // is an invalid way to check for a null pointer

• To the compiler this is not a check for a null pointer, but an equality check on two variables.
• This might work if mynull never changes in the code and the compiler optimizations constant fold the 0 into the if statement, but this is not guaranteed and the compiler has to produce at least one diagnostic message (warning or error) according to the C Standard.

• NULL pointer is guaranteed to compare equal to 0. But it doesn't have to be represented with all-zero bits.
• 根據上面列的參考資料，我的理解是：如果 header file 定義的 null pointer（NULL） 是全 0-bit，則他符合 C standard，但不一定要這樣實現（因為 NULL 是 implementation-defined）

Null Characters

• \0 is defined to be a null character, that is a character with all bits set to zero.
• \0 is (like all character literals) an integer constant, in this case with the value zero. So \0 is completely equivalent to an unadorned 0 integer constant
• 差異在於 \0 可以告訴 programmer 說："我在這裡使用空字元"

Write through / Write Back

淺談各種 cache 策略

DMA

直接記憶體存取

Cache Coherence

簡介 Memory Access, cache coherence protocol and memory barrier
Cache Coherency & I/O ordering

Different between *p[] and (*p)[]

What is the difference b/w int (*p) [10] and int *p [10]?

Reentrancy 和 Thread-safe

深入理解 Reentrancy 和 Thread-safe

資料結構-洪毅

Ch7 Search & Sort
Ch8 Hashing
Ch9 Advanced Tree Structure

Meaning of pointer + 1

int *p=(int *)(&a + 1)的理解

資工專業

Merge Sort
Quick Sort
Heap Sort
演算法與資料結構
面試參考心得
OS