2025q1 Homework1 (lab0)

contributed by < MuChengChen >

Reviewed by EricccTaiwan

1. 開發環境不須使用 shell=，使用 shell 即可。
2. 實作 queue.c 的筆記，建議補上各自功能的 commit，方便讀者們搭配著筆記閱讀程式碼。

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
• 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
• 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
• HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
• 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
• 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
• 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
• 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
• 避免使用不必要的 emoji 字元

開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0

$ lscpu
Architecture:             x86_64
CPU op-mode(s):         32-bit, 64-bit
Address sizes:          39 bits physical, 48 bits virtual
Byte Order:             Little Endian
CPU(s):                   8
On-line CPU(s) list:    0-7
Vendor ID:                GenuineIntel
Model name:             11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
CPU family:           6
Model:                140
Thread(s) per core:   2
Core(s) per socket:   4
Socket(s):            1
Stepping:             1
CPU(s) scaling MHz:   21%
CPU max MHz:          4200.0000
CPU min MHz:          400.0000
BogoMIPS:             4838.40
Flags:                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_
                      tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg f
                      ma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb cat_l2 cdp_l2 
                      ssbd ibrs ibpb stibp ibrs_enhanced tpr_shadow flexpriority ept vpid ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid rdt_a avx512f avx512dq rdseed 
                      adx smap avx512ifma clflushopt clwb intel_pt avx512cd sha_ni avx512bw avx512vl xsaveopt xsavec xgetbv1 xsaves split_lock_detect user_shstk dtherm ida arat pln
                       pts hwp hwp_notify hwp_act_window hwp_epp hwp_pkg_req vnmi avx512vbmi umip pku ospke avx512_vbmi2 gfni vaes vpclmulqdq avx512_vnni avx512_bitalg avx512_vpopc
                      ntdq rdpid movdiri movdir64b fsrm avx512_vp2intersect md_clear ibt flush_l1d arch_capabilities
Virtualization features:  
Virtualization:         VT-x
Caches (sum of all):      
L1d:                    192 KiB (4 instances)
L1i:                    128 KiB (4 instances)
L2:                     5 MiB (4 instances)
L3:                     8 MiB (1 instance)
NUMA:                     
NUMA node(s):           1
NUMA node0 CPU(s):      0-7
Vulnerabilities:          
Gather data sampling:   Mitigation; Microcode
Itlb multihit:          Not affected
L1tf:                   Not affected
Mds:                    Not affected
Meltdown:               Not affected
Mmio stale data:        Not affected
Reg file data sampling: Not affected
Retbleed:               Not affected
Spec rstack overflow:   Not affected
Spec store bypass:      Mitigation; Speculative Store Bypass disabled via prctl
Spectre v1:             Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Spectre v2:             Mitigation; Enhanced / Automatic IBRS; IBPB conditional; RSB filling; PBRSB-eIBRS SW sequence; BHI SW loop, KVM SW loop
Srbds:                  Not affected
Tsx async abort:        Not affected

如何利用 git rebase 更新 fork 的專案

Step 1:增加源專案到 remote 並命名為 "upstream"
git remote add upstream https://github.com/sysprog21/lab0-c.git

Step 2:fetch 源專案的所有分支
git fetch upstream

Step 3:利用 git rebase 將本地的 master 改寫為源專案的 master
git rebase upstream/master

Step 4:將改寫的本地 master 推回自己帳號的專案
git push origin master --force

佇列操作實作

q_new

Commit c16d97d

目的

創造空佇列

實作流程

1. 用 malloc 取得 list_head 結構體大小的記憶體空間並配置給新的 list_head 結構體指標，若記憶體取得失敗則回傳 NULL
2. 利用 INIT_LIST_HEAD 初始化 list_head 結構體指標，將指向的結構體的 next 和 prev 指向結構體本身
3. 回傳 list_head 結構體指標

q_free

Commit 7e8d20b

目的

釋放所有佇列使用到的記憶體空間

實作流程

1. 使用 while 迴圈疊代佇列的所有節點
2. 使用巨集 container_of 取得節點的位址
3. 使用 list_del 斷掉節點與佇列的連結
4. 使用 q_release_element 釋放節點使用的記憶體
5. 當釋放完所有節點使用的記憶體後釋放佇列的 head

q_insert_head

Commit f5a4f90

目的

插入新的節點到佇列的第一個節點，且節點中的 value 和 s 字串的內容相同

實作流程

1. 若 head 和 s 為 NULL 回傳 false
2. 用 malloc 取得 element_t 結構體大小的記憶體空間並配置給新的 element_t 結構體指標，若記憶體取得失敗則回傳 false
3. 用 malloc 取得 s 字串長度 +1 的記憶體空間並配置給 element_t 結構體指標指向的 element_t 結構體中的 value，若記憶體取得失敗則釋放 element_t 結構體中的 value 並回傳 false
4. 使用 strncpy 將 s 字串複製到 element_t 結構體中的 value 並在最後加上 '\0'
5. 使用 list_add 將新的 element_t 結構體連接到佇列的第一個節點並回傳 true

q_insert_tail

Commit 5f71875

目的

插入新的節點到佇列的最後一個節點，且節點中的 value 和 s 字串的內容相同

實作流程

1. 若 head 和 s 為 NULL 回傳 false
2. 用 malloc 取得 element_t 結構體大小的記憶體空間並配置給新的 element_t 結構體指標，若記憶體取得失敗則回傳 false
3. 用 malloc 取得 s 字串長度 +1 的記憶體空間並配置給 element_t 結構體指標指向的 element_t 結構體中的 value，若記憶體取得失敗則釋放 element_t 結構體中的 value 並回傳 false
4. 使用 strncpy 將 s 字串複製到 element_t 結構體中的 value 並在最後加上 '\0'
5. 使用 list_add_tail 將新的 element_t 結構體連接到佇列的最後一個節點並回傳 true

q_remove_head

Commit 27d65e9

目的

將佇列的第一個節點移除，且將節點中的 value 字串複製到字串 sp

實作流程

1. 若 head 為 NULL 或佇列為空佇列則回傳 NULL
2. 使用巨集 container_of 取得佇列第一個節點的位址
3. 若 sp 不為 NULL 則使用 strncpy 複製節點的 value 字串到字串 sp 並在最後加上 '\0'
4. 使用 list_del 斷掉節點與佇列的連結並回傳節點的位址

q_remove_tail

Commit a9b3ded

目的

將佇列的最後一個節點移除，且將節點中的 value 字串複製到字串 sp

實作流程

1. 若 head 為 NULL 或佇列為空佇列則回傳 NULL
2. 使用巨集 container_of 取得佇列最後一個節點的位址
3. 若 sp 不為 NULL 則使用 strncpy 複製節點的 value 字串到字串 sp 並在最後加上 '\0'
4. 使用 list_del 斷掉節點與佇列的連結並回傳節點的位址

q_size

Commit 275d9b5

目的

取得該佇列節點的數量

實作流程

1. 若 head 為 NULL 則回傳 0
2. 利用 list_for_each 疊代佇列中所有的節點並加總節點的數量，最後回傳該數量

q_delete_mid

Commit 03f15f5

目的

移除並釋放佇列中間的節點

實作流程

1. 若 head 為 NULL 或佇列為空佇列則回傳 false
2. 若佇列只有一個節點則移除並釋放此節點
3. 若佇列不只有一個節點則使用快慢指標的方法找到佇列中間的節點
4. 使用巨集 container_of 找到該節點的位址
5. 使用 list_del 斷開節點和佇列的連結
6. 釋放節點所使用的記憶體並回傳 true

q_delete_dup

Commit 0adad8c

目的

移除並釋放佇列中有相同value的相鄰節點

實作流程

1. 若 head 為 NULL 或佇列為空佇列回傳 false
2. 若只有一個節點回傳 true
3. 配置10個 char 大小的記憶體提供暫時存放節點的 value 的空間
4. 使用 list_for_each_safe 疊代佇列的所有節點
5. 若此節點的 value 與前一個節點(暫時存放的節點的 value )相同或是與下一個節點的 value 相同則暫時存放此節點的 value ，斷開此節點與佇列的連結並且釋放此節點使用的記憶體
6. 若此節點的 value 與前一個節點不同或是與下一個節點的 value 不同則將暫時存放節點的空間都存入空字串
7. 最後釋放配置的10個 char 大小的記憶體並回傳 true

q_swap

Commit d5776aa

目的

交換佇列中每兩個節點的位置

實作流程

1. 使用 list_for_each_safe 疊代佇列中的每個節點，將 node 和 safe 的位置交換
2. 若全部節點都疊代過了或是只剩下一個節點還沒疊代則停止疊代

q_reverse

Commit 36d9f0c

目的

倒置佇列中的節點

實作流程

1. 使用 list_for_each_safe 疊代佇列中的所有節點
2. 使用 list_move 將每個疊代到的節點移動成佇列的第一個節點

q_reverseK

Commit 00a9b70

目的

將佇列中每 k 個節點視為一個要倒置的 list ，若疊代至最後不足 k 個節點則不進行倒置

實作流程

1. 使用 list_for_each_safe 疊代佇列中的所有節點
2. 使用 list_move 將每個疊代到的節點移動成當前要倒置的 list 的第一個節點
3. 檢查是否已倒置 k 個節點，若已倒置 k 個節點則檢查剩下在佇列中未疊代到的節點數量是否大於或等於 k ，若是則紀錄此 list 的最後一個節點為接下來的 list 中要移動到的位置的前一個節點

q_sort

Commit b9d003f

目的

將佇列中的節點依節點的 value 進行升冪或降冪的排序

實作方法

merge sort

實作流程

1. 將佇列的 head 分離，並初始化 head
2. 將佇列進行 merge sort 排序，以分治法實作
3. 使用快慢指標找到佇列的中點並以此分割成兩個佇列，以此遞迴分割直到每個佇列只剩下一個節點或沒有節點
4. 將分割完的佇列使用 strcmp 比較兩個佇列節點之間的 value 並依此排序與合併，直到合併成一個排序好且完整的佇列
5. 將一開始分離的 head 接上佇列

q_ascend

Commit 873049d

目的

將節點中的佇列依升冪的順序排序，若是右邊節點的 value 等於左邊節點的 value 則移除並且釋放此節點

實作流程

1. 使用 q_sort 進行升冪排序
2. 使用 list_for_each_safe 疊代排序好的佇列中的節點
3. 使用 strcmp 比較是否右邊節點的 value 等於左邊節點的 value ，若是則使用 list_del 斷掉節點和佇列的連結，最後釋放節點所占用的記憶體
4. 回傳最後佇列剩下的節點總數

q_descend

Commit 78c3c0e

目的

將節點中的佇列依降冪的順序排序，若是右邊節點的 value 等於左邊節點的 value 則移除並且釋放此節點

實作流程

1. 使用 q_sort 進行降冪排序
2. 使用 list_for_each_safe 疊代排序好的佇列中的節點
3. 使用 strcmp 比較是否右邊節點的 value 等於左邊節點的 value ，若是則使用 list_del 斷掉節點和佇列的連結，最後釋放節點所占用的記憶體
4. 回傳最後佇列剩下的節點總數

q_merge

Commit bb42a1b

目的

合併所有佇列並且以升冪或降冪排序

實作流程

1. 若串聯 queue_contex_t 的佇列的 head 為 NULL 或是佇列為空佇列則回傳 0
2. 疊代所有的 queue_contex_t ，每個 queue_contex_t 含有一個佇列
3. 將疊代到的佇列與第一個佇列的 head 分離並且初始化兩個佇列的 head
4. 使用 strcmp 比較兩個佇列節點之間的 value 並依此排序與合併，直到合併成一個排序好且完整的佇列
5. 將第一個佇列的 head 接上合併好佇列
6. 若所有佇列皆已合併到第一個佇列則使用 list_for_each 疊代此佇列的所有節點以此計算節點的總數，最後回傳佇列中節點的總數

新增 shuffle 命令

Fisher–Yates shuffle 演算法

演示範例 :

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

實作 Fisher–Yates shuffle 演算法

在 console_init() 中增加 shuffle 命令

static void console_init()
{
    ...
    ADD_COMMAND(descend,
                "Remove every node which has a node with a strictly greater "
                "value anywhere to the right side of it",
                "");
    ADD_COMMAND(reverseK, "Reverse the nodes of the queue 'K' at a time",
                "[K]");
+   ADD_COMMAND(shuffle, "Shuffle the queue using the Fisher-Yates algorithm", "");
    ...
}

增加 do_shuffle 函式對 queue 實現 Fisher–Yates shuffle 演算法

commit 34c176

Pearson's chi-squared test

(1)若能符合分配的要求，「觀察值」與「期望值」的比較就不應差太多，卡方值就不會太大而落入拒絕域
(2)卡方檢定是右尾檢定
(3)卡方檢定是屬於無母數分析技巧

檢驗結果

• shuffle [1,2,3,4] 1,000,000 次以測試是否遵守 Uniform distribution

Expectation: 41666

Observation: {'1234': 41583, '1243': 41748, '1324': 41260, '1342': 41425, '1423': 41971, '1432': 41590, '2134': 41414, '2143': 42029, '2314': 41778, '2341': 41921, '2413': 41335, '2431': 41767, '3124': 41561, '3142': 41815, '3214': 41337, '3241': 41656, '3412': 41615, '3421': 41836, '4123': 41881, '4132': 41357, '4213': 41500, '4231': 42002, '4312': 41861, '4321': 41758}

chi square sum: 29.512072193155092

• $H_0$（虛無假說）: shuffle 的結果發生的機率相同，遵守 Uniform distribution
• $H_1$（對立假說）: shuffle 的結果發生的機率至少有一個不同

由於有24種可能，因此自由度是24-1=23，且

$X^2$ 為 29.512072193155092，27.14<29.512072193155092<32.01，因此由卡方分布表可以得知 P value 落在 0.25~0.1 之間

由於 P value (0.25~0.1)>alpha(0.05)，統計檢定的結果不拒絕虛無假說(

$H_0$)，也就是樣本資料不拒絕 shuffle 的結果遵循 Uniform distribution，從測試結果的圖表來看也大致符合 Uniform distribution

在測試 Fisher–Yates shuffle 演算法的腳本中 test_count 並不是真正的測試次數，test_count*4 才是真正的測試次數，因此這部分還需要修改

研讀〈Dude, is my code constant time?〉

有參考 POJU 和 陳麒升 的筆記

lab0-c 程式碼追蹤

首先看到 constant.h

#define DUT_FUNCS  \
    _(insert_head) \
    _(insert_tail) \
    _(remove_head) \
    _(remove_tail)

#define DUT(x) DUT_##x

enum {
#define _(x) DUT(x),
    DUT_FUNCS
#undef _
};

先將 DUT_FUNCS 定義成四個使用 _ 函式的巨集，再定義 DUT(x) 為展開成 DUT_x 的巨集，最後定義 _(x) 為使用 DUT(x) 的巨集，因此 enum 展開為以下形式

enum {
    DUT_insert_head,
    DUT_insert_tail,
    DUT_remove_head,
    DUT_remove_tail,
}

最後取消 ＿ 巨集

再來看到 fixture.h

/* Interface to test if function is constant */
#define _(x) bool is_##x##_const(void);
DUT_FUNCS
#undef _

先將 ＿(x) 定義成資料型態為 bool 的 is_x_const(void) 函式，再使用 DUT_FUNCS 巨集定義 is_insert_head_const(void) 、is_insert_tail_const(void) 、 is_remove_head_const(void) 、 is_remove_tail_const(void) ， 最後取消 ＿ 巨集

再來看到 fixture.c

#define DUT_FUNC_IMPL(op)                \
    bool is_##op##_const(void)           \
    {                                    \
        return test_const(#op, DUT(op)); \
    }

#define _(x) DUT_FUNC_IMPL(x)
DUT_FUNCS
#undef _

定義 DUT_FUNC_IMPL(op) 為 is_op_const(void) 且返回 test_const(op, DUT(op))。最後定義 _(x) 為使用 DUT_FUNC_IMPL(x) 的巨集，使用 DUT_FUNCS 執行完 _(x) 後取消 ＿ 巨集

再來看到 test_const 函式

static bool test_const(char *text, int mode)
{
    bool result = false;

    init_once();

    for (int cnt = 0; cnt < TEST_TRIES; ++cnt) {
        printf("Testing %s...(%d/%d)\n\n", text, cnt, TEST_TRIES);
        for (int i = 0; i < ENOUGH_MEASURE / (N_MEASURES - DROP_SIZE * 2) + 1;
             ++i)
            result = doit(mode);
        printf("\033[A\033[2K\033[A\033[2K");
        if (result)
            break;
    }

    for (size_t i = 0; i < DUDECT_TESTS; i++) {
        free(ctxs[i]);
        ctxs[i] = NULL;
    }

    return result;
}

init_once() 初始化 l 並且檢查 ctxs 陣列中每個元素是否都有被初始化
doit 函式

static bool doit(int mode)
{
    int64_t *before_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
    int64_t *after_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
    int64_t *exec_times = calloc(N_MEASURES, sizeof(int64_t));
    uint8_t *classes = calloc(N_MEASURES, sizeof(uint8_t));
    uint8_t *input_data = calloc(N_MEASURES * CHUNK_SIZE, sizeof(uint8_t));
    int64_t *percentiles = calloc(NUM_PERCENTILES, sizeof(int64_t));

    if (!before_ticks || !after_ticks || !exec_times || !classes ||
        !input_data || !percentiles) {
        die();
    }

    prepare_inputs(input_data, classes);

    bool ret = measure(before_ticks, after_ticks, input_data, mode);
    differentiate(exec_times, before_ticks, after_ticks);
    prepare_percentiles(exec_times, percentiles);
    update_statistics(exec_times, classes, percentiles);
    ret &= report();

    free(before_ticks);
    free(after_ticks);
    free(exec_times);
    free(classes);
    free(input_data);
    free(percentiles);

    return ret;
}

• C23 [7.24.3.2] The calloc function

  ​​​​void *calloc(size_t nmemb, size_t size);
  

  • Description : The calloc function allocates space for an array of nmemb objects, each of whose size is size. The space is initialized to all bits zero.
  • Returns : The calloc function returns either a pointer to the allocated space or a null pointer if the space cannot be allocated or if the product nmemb * size would wraparound size_t.

  calloc 會配置 nmemb 個元素的陣列，每個元素的大小為 size。當無法配置時回傳 NULL 指標，成功配置時回傳配置記憶體位置的指標。

  再來看到 die() 函式

  ​​​​static void __attribute__((noreturn)) die(void)
  ​​​​{
  ​​​​    exit(111);
  ​​​​}
  

• GCC [6.36] Specifying Attributes of Variables
  The keyword __attribute__ allows you to specify special attributes of variables or structure fields. This keyword is followed by an attribute specification inside double parentheses. Some attributes are currently defined generically for variables. Other attributes are defined for variables on particular target systems. Other attributes are available for functions (see Function Attributes) and for types (see Type Attributes). Other front ends might define more attributes (see Extensions to the C++ Language).

  __attribute__ 是GCC的一種編譯器指令，後會跟著雙重括號，括號內部會有屬性，而屬性有三種，分別為函式屬性、變數屬性和型別屬性

  • Attribute Syntax : noreturn
    • A few standard library functions, such as abort and exit, cannot return. GCC knows this automatically. Some programs define their own functions that never return. You can declare them noreturn to tell the compiler this fact. For example
    ​​​​​​​​void fatal () __attribute__ ((noreturn));
    
    ​​​​​​​​      void
    ​​​​​​​​      fatal (/* ... */)
    ​​​​​​​​      {
    ​​​​​​​​        /* ... */ /* Print error message. */ /* ... */
    ​​​​​​​​        exit (1);
    ​​​​​​​​      }
    

    • The noreturn keyword tells the compiler to assume that fatal cannot return. It can then optimize without regard to what would happen if fatal ever did return. This makes slightly better code. More importantly, it helps avoid spurious warnings of uninitialized variables.
    • The noreturn keyword does not affect the exceptional path when that applies: a noreturn-marked function may still return to the caller by throwing an exception or calling longjmp.
    • Do not assume that registers saved by the calling function are restored before calling the noreturn function.
    • It does not make sense for a noreturn function to have a return type other than void.

    noreturn 是函式屬性，這個屬性是對編譯器說明此函式沒有回傳的特性，或是因為處理 fatal 的情況所以最後 exit() 不會回傳。以 die() 函式來說，函式內部直接 exit(111) 所以確定函式不會回傳，所以加了 noreturn 的屬性。

    標有 noreturn 屬性的函式有可能仍然會以 exception 或 calling longjmp 的方式回傳回 caller ，但不能假設暫存 calling function 的暫存器會被保存下來。

    若 noreturn 屬性的函式不是 void 是不合理的。

  看到 prepare_inputs 函式

  ​​​​void prepare_inputs(uint8_t *input_data, uint8_t *classes)
  ​​​​{
  ​​​​    randombytes(input_data, N_MEASURES * CHUNK_SIZE);
  ​​​​    for (size_t i = 0; i < N_MEASURES; i++) {
  ​​​​        classes[i] = randombit();
  ​​​​        if (classes[i] == 0)
  ​​​​            memset(input_data + (size_t) i * CHUNK_SIZE, 0, CHUNK_SIZE);
  ​​​​    }
  
  ​​​​    for (size_t i = 0; i < N_MEASURES; ++i) {
  ​​​​        /* Generate random string */
  ​​​​        randombytes((uint8_t *) random_string[i], 7);
  ​​​​        random_string[i][7] = 0;
  ​​​​    }
  ​​​​}
  

  其中 randombytes 函式

  ​​​​int randombytes(uint8_t *buf, size_t n)
  ​​​​{
  ​​​​#if defined(__linux__) || defined(__GNU__)
  ​​​​#if defined(USE_GLIBC)
  ​​​​    /* Use getrandom system call */
  ​​​​    return linux_getrandom(buf, n);
  ​​​​#elif defined(SYS_getrandom)
  ​​​​    /* Use getrandom system call */
  ​​​​    return linux_getrandom(buf, n);
  ​​​​#else
  ​​​​    /* When we have enough entropy, we can read from /dev/urandom */
  ​​​​    return linux_urandom(buf, n);
  ​​​​#endif
  ​​​​#elif defined(BSD)
  ​​​​    return bsd_randombytes(buf, n);
  ​​​​#else
  ​​​​#error "randombytes(...) is not supported on this platform"
  ​​​​#endif
  ​​​​}
  

• GCC [4.2.1] Ifdef
  The simplest sort of conditional is

  ​​​​#ifdef MACRO
  
  ​​​​controlled text
  
  ​​​​#endif /* MACRO */
  

  This block is called a conditional group. controlled text will be included in the output of the preprocessor if and only if MACRO is defined. We say that the conditional succeeds if MACRO is defined, fails if it is not.

  The controlled text inside of a conditional can include preprocessing directives. They are executed only if the conditional succeeds. You can nest conditional groups inside other conditional groups, but they must be completely nested. In other words, ‘#endif’ always matches the nearest ‘#ifdef’ (or ‘#ifndef’, or ‘#if’). Also, you cannot start a conditional group in one file and end it in another.

  Even if a conditional fails, the controlled text inside it is still run through initial transformations and tokenization. Therefore, it must all be lexically valid C. Normally the only way this matters is that all comments and string literals inside a failing conditional group must still be properly ended.

  The comment following the ‘#endif’ is not required, but it is a good practice if there is a lot of controlled text, because it helps people match the ‘#endif’ to the corresponding ‘#ifdef’. Older programs sometimes put MACRO directly after the ‘#endif’ without enclosing it in a comment. This is invalid code according to the C standard. CPP accepts it with a warning. It never affects which ‘#ifndef’ the ‘#endif’ matches.

  Sometimes you wish to use some code if a macro is not defined. You can do this by writing ‘#ifndef’ instead of ‘#ifdef’. One common use of ‘#ifndef’ is to include code only the first time a header file is included. See Once-Only Headers.

  依照上面的例子，當 MACRO (也就是巨集)被定義 controlled text 才會被執行成功， controlled text 可以包含前置處理器指示詞，如 ＃define 、 #elif 等等。 Ifdef 也可以組織成巢狀結構，而 #endif 會和最近的 #ifdef (或 #ifndef ,或 #if )組合成一個完整的 conditional group ，但不能跨文件。

  若條件不成立， controlled text 還是會被轉換和分詞，因此 controlled text 還是要是合法的 C 語言並且要適當的結束。

  #endif 不是必要的，但有助於辨別 conditional group 。

  若是要使用的程式碼中含有未定義的巨集可以善用 Ifdef 結構。

參考 Pre-defined C/C++ Compiler Macros
__linux__ 和 __GNU__ 為 C 和 C++ 編譯器的預定義巨集。預定義巨集可以讓編譯器確認目前的系統是哪種編譯器和作業系統，在寫可攜式軟體時很有用

USE_GLIBC 在以下程式碼中被定義

#if (defined(__linux__) || defined(__GNU__)) && defined(__GLIBC__) && \
    ((__GLIBC__ > 2) || (__GLIBC_MINOR__ > 24))
#define USE_GLIBC
#include <sys/random.h>
#endif