contributed by < idoleat
>
問題 2 :考慮以下程式碼: char s[64]; 試問 s == &s
是否成立?搭配〈你所不知道的 C 語言:指標篇〉的描述,佐以 C 語言規格來解釋
若是編譯上面的程式碼,不論是宣告在 global 還是函式中皆會得到警告
首先思考 s 什麼時候會被當成指標?
C11 6.3.2.1 Lvalues, arrays, and function designators 中第三點
Except when it is the operand of the sizeof operator, the _Alignof operator, or the unary & operator, or is a string literal used to initialize an array, an expression that has type "array of type" is converted to an expression with type "pointer to type" that points to the initial element of the array object and is not an lvalue. If the array object has register storage class, the behavior is undefined.
由此可知左邊的 s 是指向 char array 的第一個元素的指標,右邊的 s 是 array of char,由 unary operator &
取址後與左邊的 s 所指之地址相同,s == &s
為 true
起初在查閱規格書之前猜想如果兩邊的 s 都作為 expression 因此都是指標,則 s == &s
是在判斷指標指的地址與指標本身的地址是否一樣,查閱完規格書之後思考那如果是這樣的規格會發生什麼事?若是作為 expression 都解讀為指標,那得到一個指標時就需要再額外判斷此指標究竟是指向一個 object 還是 array of object
由 s == &s
延伸思考,編譯器實作上是否可以在宣告 array of type 時額外配置一個指標指向該 array? 如此可以滿足 s 作為 expression 時都是指標,此時的 s == &s
則是 false
若是以 GDB 觀察:
GDB 的解釋方法似乎有太過聰明?或是說 GDB 並沒有把 s 當作 expression? 需要去閱讀 GDB 文件確認一下
一個序列是一張全連接圖退化而成的子圖,一張 的全連接圖可以退化成 種不同的序列,排序是從一個子圖演變成另一種子圖,過程中各節點會斷開邊或建立邊。假設邊上有權重,權重為相鄰節點之間的數值差,一個已排序的序列其權重合的絕對值為所有子圖的最小值,並且剛好為首尾節點的數值差。
思考:將子圖視為一種狀態,要如何找出走到已排序狀態的路徑?
目前已知性質:
想法一:先接回全連接圖,再逐步斷開邊,直至一個序列。如何挑邊?會不會陷入 local minimum? 需要 heuristic?
在建立空佇列時會配置結構體 queue_context_t
,並根據需要初始化每個欄位,其中的 list head 即為佇列的 head,但不包括 ID。我不確定 ID 的使用方式,所以稍後會更新它。
如果傳入的 head 是 NULL
會回傳 false
作為失敗的操作。成功配置且插入的節點會使用 strdup
配置新的字串並從傳入的字串複製內容。若字串配置失敗也會回傳 false
作為失敗的操作並一併釋放已配置的記憶體。Cppcheck 這時會偵測到函式宣告中的字串沒有被修改到所以需要被標示為 const
,不過修改 queue.h
會造成 commit 時 check sum 失敗並得到不得修改 queue.h
的警告,所以我使用 // cppcheck-suppress constParameterPointer
暫時抑制了此項檢查。
在佇列的建立與節點插入時若遇到配置失敗皆會導致操作失敗,不過不包含作業系統 over commit 的情況 (TODO: 該怎麼處理 over commit 的狀況?) vacantron提示了 Linux kernel 內即有文件描述之,不過他被歸類在 legacy documentation,屬筆記、mailing list 回覆等類型所以無法百分之百仰賴其解釋。但是同時我也發現我對 memory paging 及 mapping 理解不足,需要去閱讀 CS:APP Ch9
TODO: 設計會發生 over commit 的環境
持續思考間接指標及更多層間接指標所創造的幻象 (illusion),如何利用此特性更簡潔統一的操作?
如果傳入的 head 是 NULL
或佇列為空會回傳 false
作為失敗的操作。注意 list_empty
不檢查 head
是否為 NULL
。節點在此只是斷開連結並回傳指向此節點的指標及複製節點內字串給呼叫者做後續動作。注意 man strncpy
中 CAVEATS 段落提到 "The name of these function is confusing" ,該處舉例並說明補上 0 及裁剪超出指定長度字串的行為。對於 bufsize 不大於節點內字串 buffer size 的情況都須補上空字元作為結尾。另外,list_del
實質上是 remove
走訪每個節點釋放該節點及該節點內成員所指向的記憶體。在迭代器所指的元素直接釋放或是使用 q_remove 逐一釋放都會造成迭代器遺失下一個節點的地址,因此需要保留可以存取下一個節點的途徑,for_each_safe
以及 for_each_entry_safe
使用額外的指標先行紀錄下一個節點的位址。最後 queue_context_t
也要釋放。若 head
是 NULL 則視為無效操作。此處的額外宣告的迭代器及 safe 指標若是還會為他處所用記得先設為 NULL 以免 double free
直覺上是使用 hash table,但是需要考慮到 hash table 會需要使用記憶體,若為了節省記憶體開銷 table size 開很小碰撞機率很高,會逐漸退化為鏈結串列,開太大又使用太多記憶體,這在 Linux kernel 內是不樂見的。不過這邊 dedup 的前提是鏈結串列是已經排序過的,有相同字串內容的結點會相鄰排列。在逐一走訪每個結點時檢查下一個節點是否也一樣內容的字串,若有則移除並釋放當下結點,並標記下一結點為也需要移除與釋放,以此讓有相同字串內容的結點最後一個在檢查到與下一個結點有不同內容的字串時還是會自我移除與釋放。本來想用記憶體位置對齊的特性,將標記放在記憶體位置最低位元,但仍一直觸發 segmentation fault ,在找出原因之前先以 bool flag 標記
實作方式為 bottom-up merge sort,將子鏈結串列成對合併,其長度為 2 的冪,從零次方開始。每次合併完所有成對的鏈結串列時,子鏈結串列長度都會加倍,直到沒有 list head
可以合併為止。
當鏈結串列長度不是 2 的冪時,有兩種情況
合併的方法為將右子鏈結串列取出作為一個儲存於 stack 上的新鏈結串列,並依據 strcmp
的結果將節點逐一加回左子鏈結串列。注意要維持 stable sort 的特性,比較結果相同的情況下原本在右子鏈結串列的節點要維持放在右邊。取右子鏈結串列的原因為剩餘的節點都在右側,如此可以取較少數量,而非左側完整長度的子鏈結串列。當然要取左子鏈結串列也是可行的
使用此將右子鏈結串列取出作為一個新鏈結串列來合併的原因是要善用 list API 來達到更好的 semantic 也比較好維護,雖然建立新鏈結串列又再插入有很多多餘的指標內容修改,但是能避免為了省去那些指標內容修改而帶來的更多的特殊情況。例如以下失敗的嘗試,由於長度太長這邊用 spoiler 折疊,這還不包括一些還沒處理的特殊狀況,即便善用間接指標,也還是相當冗長不易讀。在分析上,合併兩個子鏈結串列的行為即為建立(長度 -1) 個邊,不是跨串列就是同串列,雖然看似簡單但是在指標內容修改上很容易寫到不易確認行為。使用 list API 至少是透過已知安全的操作來建構,其整個操作也會是安全的
q_sort
值得提到的是,目前測試通過的實作中 bool descend
,是以 descend * 2 - 1
轉換為不是 1 就是 -1 的整數,與 strcmp
回傳值相乘,這樣遞增遞減都使用同一段程式碼不用多寫
接下來要研究 Linux 核心鏈結串列的實作機制,及其高效的排序實作,並再多加實作 作業二 中的排序方法還有我在重新認識 quick sort 時提出來的新嘗試 vbsort
,並在修正 qtest 及其測試方法後進行效能比較
lib/list_sort.c
:除了複製貼上函式以外,u8
在 lib/type.h
中沒有定義 __BIT_TYPES_DEFINED__
的情況為 u_int8_t
,其餘為 uint8_t
。前者為相容不同 C 函式庫而定(待考證),後者為 C 標準函式庫中的型別,在此選用 uint8_c
。likely
與 unlikely
的巨集也需要一併移植,另外我注意到如果 include/linux/compiler.h
有開啟 CONFIG_TRACE_BRANCH_PROFILING
的話,會搭配 __branch_check__
巨集來 profile 分之預測。其中 profiling 標的除了預設的 none 之外分為 annotated 及 all branches,likely
及 unlikely
即屬前者。可在 kernel/trace/Kconfig
見到使用說明及注意事項,以及更多的 profiling 選項。。Kernel Build System 文件紀錄了如何設置(?) kernel,之前沒耐心只會用 allconfig 或是發行版的預設 config。compiler.h
也提供了以 __notrace
為後綴的巨集來躲避 tracing,在 6.8.1 中只在 include/linux/jump_label.h
見其使用If the merge is highly unbalanced (e.g. the input is already sorted), this loop may run many iterations. Continue callbacks to the client even though no element comparison is needed, so the client's cmp() routine can invoke cond_resched() periodically.
if non-preemptive…
Q.put(merge(Q.get_head(), Q.get_tail()))
測試指標為
測試資料
修正 dudect.c
假設現有一長度為 的雙向環狀鏈結串列,定義一階間接指標為序列 ,序列內成員 型別皆為 struct list_head *
,二階間接指標為序列 ,序列內成員 型別皆為 struct list_head **
, 階間接指標為序列 以此類推, 為原雙向環狀鏈結串列。 經由 動作映射(?)(map) 為 (), 經由 動作投影 (project) 回 ,可視為套用 動作之變更,二次投影可記為 或 ,以此類推,至多投影回 。
對 成員 XOR 1 會得到 , 可定義為
其中 表示 階間接指標為序列中第 成員, 則表示取址 (address of),假使目前為 映射到 可實作為
不過我們無法直接更改函式簽名,所以將真正的 q_swap()
作為此實作方法(將名稱改為 __q_swap
)的 driver code
對於一般投影回非 的前一階的作法為逐一 dereference 指標覆蓋原有的前一階指標,例如
延續假設為 與 之間的操作, 投影的方法,此處重新連結串列是投影回 才需要做的操作
注意 __q_swap
配置的 S1
需要被釋放,再上個程式碼片段中的 S3
也是,至於是在投影的時候就釋放還是在 driver code 明確 (explicit) 釋放需要多使用間接堆疊才能知道 best practice 是什麼。由於 qtest.c
中do_swap
將 noalloc_mode
設為 true
所以此實作無法使用
可以更改為只使用 stack 上的空間,不過缺點就是需要將要執行的操作連續做完,stack frame 一個一個往上疊,然後在結束 stack frame 時再一個一個投影回來(或一次投影回 )
推廣此實作至 與 ,需要藉由 macro 來生成投影函式定義及宣告中對應的指標層級
以上是失敗的 C macro 嘗試。此處意圖是解析指定的 k ,依據各 bit 的狀況取對應的 *
數量組成長度為 k 的連續 *
嘗試使用 GNU M4 macro processor 撰寫
向左對齊?向右對齊?
more cache friendly
可定義為
思考中
設計的精神上是盡可能讓所有不衝突事件同時發生,以提高平行度,僅協調衝突事件。使用間接堆疊可簡化操作,不須混雜同步上的邏輯,映射歸映射,協調歸協調
所有操作皆透過單一映射函式修改
about debuginfod
有意圖的從已排好的序列打亂是不是就可以控制亂數的分佈和 entropy? 每一步打亂都可以算出 entropy 加多少
Two Choices
Units of measure is sort of related in that we usually prefer the unit tags have no runtime cost (e.g. boxing), but different in that achieving that cost savings needs significant compile-time machinery
e.g. multiplying 2^kg * 1.5^m is valid and produces 3^kg.m but 2^kg + 1.5^m is an error
The exponents need to live in type space, but the coefficients can be in term space
David Chrisnall
while
的寫法省略兩行,閱讀上也直觀的就是一個逐一走訪的 statementremove
但是用途說明的註解標題寫 remove
描述寫 delete
,後者為誤用list_for_each_entry_safe
可以用了,裡面再接著 list_del
也是足夠 semantic,不過既然都要 remove
直到串列為空那就不用 list_del
維持 prev
的正確?while
寫法都換成新提出的巨集,數量相當驚人,大家不知道有 list_for_each_entry_safe
可以用嗎?list_splice_init
把東西搬過去,而避免會需要在整個 while loop 中都拿著 lock(這邊我的理解是既然都要整個清空了就不要還拿著 lock 卡住別人,把東西搬到旁邊去做)。對於中途可能會跳出去做其他事情可以用 list_for_each_entry_safe
並在迴圈的最後做 list_del
, Hmm? (這個我不懂為什麼要強調放最後)likely
與 unlikely
的使用,我有個疑問是那如果開發者誤用而導致該在前面的 code block 被放在後面怎麼辦? 我們需要有測試來指出這些分支預測與 L1i cache 命中的情形。而 PGO 提供另一種改善方式,依據實際執行的結果來調整分支,參見 每位程式開發者都該有的記憶體知識 Ch 6.2.2 與 Ch 7.4 的說明。不過需要注意使用 PGO 執行的代表工作若無法反應程式碼的常見使用情形則無法發揮最佳化,不如手動指定 likely
與 unlikely
並多測試參見 LWN Likely unlikely()s,提到 Steven Rostedt 在 2010 年對 Linux 核心的統計數據,呈現若干誤用 unlikely
的狀況:
"correct a total of 1909540379 times and incorrect 1270533123 times, with a 39% being incorrect"
由於現代處理器應用場景多元,當初 Linux 核心開發者針對特定的工作負載而指定的 unlikely
可能不適用新的情境,另外,現在處理器的分支預測能力也相當強,就算不用特別提示編譯器最佳化,往往性能也相當好,因此 unlikely
僅該在開發者相當確定時使用。
延伸閱讀: How branches influence the performance of your code and what can you do about it?
git blame
查閱了定義 LIST_POISON
的 include/linux/poison.h
(我們想知道這些奇怪的數字到底是怎麼決定的,有些很有梗有些很隨便),發現了 RED_INACTIVE
及 RED_ACTIVE
是針對 slab 定義的。slab 已經於 6.5.0 正式淘汰並移除大量程式碼,目前 6.8.1 中也沒有見到其使用,而 slub 中使用的是以 SLUB_
為前綴的毒藥。看來這兩個是可以移除的巨集?a newly recreated shell had to close all its open files both to get rid of any open files left by the command just executed and to rescind previous IO redirection
pstree
的結果的圖中,直線是 fork ,那橫線是指什麼?execve
甚至可以在讀取到文字檔的時候切換到 interpreter mode!)
這段程式碼在 execve()
前皆於 parent 與 child process 中執行,所以在有成功 fork()
的情況下 parent 會進入第一個 else if 進行等待,child 會進入 else 載入對應的檔案。execve
會載入 elf 覆蓋現有的記憶體空間,如果不 fork 的話會直接覆蓋掉 process 當下的執行狀態不會再跳回來 shell,一如 Ken Unix 中的覆蓋clone()
建立行程會需要做出什麼調整,execve
也可以改用 glibc 包裝好的 exec
,或是使用 posix_spawnp()
一次做完 fork
, exec
與 housekeeping steps (?)select
的使用lib/list_sort.c
不實作為 concurrent merge sort
sysctl -w vm.max_map_count=262144
才不會 crash,而 Arch Linux 也將調大預設 vm.max_map_count
以增進這類應用場景的體驗
since there will be more elements in the VM red-black tree, all operations on the VMA will take longer. The slow-down of most operations is logarithmic, e.g. further mmap's, munmap's et al. as well as handling page faults (both major and minor). Some operations will slow down linearly, e.g. copying the VMAs when a new process is forked.
char s[] = "hello";
gcc 會把 string literal 複製到 stackchar s[64] = "hello";
gcc 會放多長的字串在 .rodata? 64 byte? 6 byte?對於以上三點進行實驗:
以下 func()
皆在於 main()
中呼叫
ELF 格式皆為 elf64-x86-64
1. char *p = "hello"
.rodata
中 0: 68 65 6c 6c 6f
,對照 ASCII Code 查詢即可得知從 0 的位置開始放了五個字元 h
e
l
l
o
,但是後面反組譯為 push $0x6f6c6c65
相當令人困惑!
2. char s[] = "hello";
.text
中 17: c7 45 f2 68 65 6c 6c movl $0x6c6c6568,-0xe(%rbp)
以及 1e: 66 c7 45 f6 6f 00 movw $0x6f,-0xa(%rbp)
,movl
xx待查閱 x86 指令格式xx,movw
xx待查閱 x86 指令格式xx,$0x6c6c6568
(倒過來放?),h
e
l
l
4 byte 先放,再放 o
,因為 CPU 一次寫入 4 byte。這兩道指令將 string literal 複製進堆疊
而 .rodata
中並沒有 string literal ,自然也沒有從 .rodata
複製到 stack 上,與教材中所述不符。但是參照規格書 6.4.5 "hello" 符合 string literal 的語法,應置於 static storage 中。由此可以推斷,gcc 對他做了最佳化,並不把他視為 string literal 處理?然而關閉最佳化後 關閉最佳化後仍然是置於 objdump -D
結果仍相同.text
。
此處應該要思考 static storage 是指什麼?
Executable and shared object files statically represent programs.
TEXT_SECTION_ASM_OP
A C expression whose value is a string, including spacing, containing the assembler operation that should precede instructions and read-only data. Normally"\t.text"
is right.
READONLY_DATA_SECTION_ASM_OP
A C expression whose value is a string, including spacing, containing the assembler operation to identify the following data as read-only initialized data.
比較有趣的是 gcc 3.4 的文件 有一個READONLY_DATA_SECTION
巨集會在 target 沒有唯獨區塊也不把資料放在 text 的情況下把資料放進.data
.init
, .text
, .rodata
為唯讀以此推斷,.text
及 .rodata
皆為 static storage。所以是我誤會 你所不知道的 C 語言:指標篇 「重新探討字串」段落中 read-only data section 的意思,不可以直接解讀為 .rodata
section
另外,GCC 也支援透過 __attribute__
自訂資料存放的 section,但僅限於 global variables,而且一樣要注意 char *
與 char[]
的區別
Normally, the compiler places the objects it generates in sections like data and bss. Sometimes, however, you need additional sections, or you need certain particular variables to appear in special sections, for example to map to special hardware. The section attribute specifies that a variable (or function) lives in a particular section.
3. char s[64] = "hello";
(C99) 6.4.5p5
In translation phase 7, a byte or code of value zero is appended to each multibyte character sequence that results from a string literal or literals(66). The multibyte character sequence is then used to initialize an array of static storage duration and length just sufficient to contain the sequence.
先不論第二個實驗的結果,照規格書所述空間會剛好足夠容納 multibyte character sequence,以此推斷只會有 6 byte 在 .rodata
上方輸出結果與第二個實驗一樣,沒有 string literal 儲存於 .rodata
中。接續第二個實驗的結論,我的問題可以回答為:「string literal 一樣位於 static storage 中,在 .text
,並在執行時期將字傳內容複製到 64 byte 連續記憶體的低位,並將剩餘空間補上 0」(但是這邊用 movabs $0x6f6c6c6568,%rax
,第二個實驗中卻是用 movl
movw
)