# Circular symbol 在 linker 下的處理方式說明
## 問題

gcc 在產生執行檔時為何要有兩個下面的參數

--push-state
--as-needed
-lgcc_s
--pop-state

gcc 在產生執行檔完整指令(Ubuntu 18.04.2)

/usr/bin/ld
-plugin
/usr/lib/gcc/x86_64-linux-gnu/7/liblto_plugin.so
-plugin-opt=/usr/lib/gcc/x86_64-linux-gnu/7/lto-wrapper
-plugin-opt=-fresolution=/tmp/ccCwkJOE.res
-plugin-opt=-pass-through=-lgcc
-plugin-opt=-pass-through=-lgcc_s
-plugin-opt=-pass-through=-lc
-plugin-opt=-pass-through=-lgcc
-plugin-opt=-pass-through=-lgcc_s
--sysroot=/
--build-id
--eh-frame-hdr
-m
elf_x86_64
--hash-style=gnu
--as-needed
-dynamic-linker
/lib64/ld-linux-x86-64.so.2
-pie
-z
now
-z
relro
-o
hello
/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/Scrt1.o
/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/crti.o
/usr/lib/gcc/x86_64-linux-gnu/7/crtbeginS.o
-L/usr/lib/gcc/x86_64-linux-gnu/7
-L/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu
-L/usr/lib/gcc/x86_64-linux-gnu/7/../../../../lib
-L/lib/x86_64-linux-gnu
-L/lib/../lib
-L/usr/lib/x86_64-linux-gnu
-L/usr/lib/../lib
-L/usr/lib/gcc/x86_64-linux-gnu/7/../../..
/tmp/ccinSYzz.o
-lgcc
--push-state
--as-needed
-lgcc_s
--pop-state
-lc
-lgcc
--push-state
--as-needed
-lgcc_s
--pop-state
/usr/lib/gcc/x86_64-linux-gnu/7/crtendS.o
/usr/lib/gcc/x86_64-linux-gnu/7/../../../x86_64-linux-gnu/crtn.o

## 回答
Credit: Kito Cheng

要把整件事講清楚有點長, 其實有點懶得回不過同事討論到把他回完吧
在開始講之前先說明幾點事:
- `ld`, `ld.gold` 跟 `ld.bfd` 行為可能不一樣, 因為我不是 linker 專家而且又懶得考究每個 linker 行為所以只說明 `ld.bfd`, `-fuse-ld=bfd` 可以確保你用的 linker 是 bfd
- `--as-needed` 看起來 gcc 很雞婆的會自己掛上去了, 也因為我懶得去查證 gcc 啥時變這樣或一直都這樣, 所以為了確保狀態在最前面掛 `-Wl,--as-needed / -Wl,--no-as-needed`

> 連結兩三次是因為library之間的function可能互call.

連結兩三次`libgcc` 跟上面這件事有什麼關係要從 linker 實作講起了,linker 為了效能考量會依先後順序開始蒐集 undef symbol, 然後去後續的 library 找 undef 的 symbol 來避免需要多次掃描 input library. 但 static/dynamic library 的行為又會有點不一樣...

這個直接舉例來說明比較快,

首先我們先來看 shared library 的情況, 假設你現在有兩個 so,

* `libfoo.so`
* `libbar.so`

libfoo.c

int a()
{
  return 0;
}

libbar.c

int a();
int b()
{
  return a();
}

main.c

#include <stdio.h>
int b();
int main()
{
  printf("%d\n", b());
  return 0;
}

產生 shared library

gcc -shared -fPIC libfoo.c -o libfoo.so
gcc -shared -fPIC libbar.c -o libbar.so

四種編譯方式

gcc -Wl,--as-needed -fuse-ld=bfd main.c -L . -lfoo -lbar # 1. Undef ref to `a`
gcc -Wl,--as-needed -fuse-ld=bfd main.c -L . -lbar -lfoo # 2. OK
gcc -Wl,--no-as-needed -fuse-ld=bfd main.c -L . -lfoo -lbar # 3. OK
gcc -Wl,--no-as-needed -fuse-ld=bfd main.c -L . -lbar -lfoo # 4. OK

情境討論
1. --as-needed mode:
main 有 undef symbol b
掃描到 foo 發現沒人 ref 到, 丟掉
掃描到 bar 發現有人 ref 到 link 進來 (main.c 要 b)
a 因為掃到 foo 的時候還沒人要所以丟掉, 後來要用但來不及了

2. --as-needed mode
main 有 undef symbol b
掃描到 bar 發現有人 ref 到 link 進來 (main.c 要 b)
掃描到 foo 發現有人 ref 到 link 進來 (bar 要 a)
Done

3. bar 跟 foo 都 link 進來所以事情都很順利不解釋
3. bar 跟 foo 都 link 進來所以事情都很順利不解釋

接著我們來看 static library 的情況, 假設你現在有兩個 .a,

* libfoo.a
* libbar.a

libfoo.c

int a()
{
  return 0;
}

libbar.c

int a();
int b()
{
  return a();
}

main.c

#include <stdio.h>
int b();
int main()
{
  printf("%d\n", b());
  return 0;
}

產生libfoo.a 以及 libbar.a

gcc -c libfoo.c -o libfoo.c.o
ar rcs libfoo.a libfoo.c.o
gcc -c libbar.c -o libbar.c.o
ar rcs libbar.a bar.c.o

四種編譯方式

# 加 -static 確保連結 static library
gcc -Wl,--as-needed -fuse-ld=bfd main.c -static -L . -lfoo -lbar # 1. Undef ref to `a`
gcc -Wl,--as-needed -fuse-ld=bfd main.c -static -L . -lbar -lfoo # 2. OK
gcc -Wl,--no-as-needed -fuse-ld=bfd main.c -static -L . -lfoo -lbar # 3. Undef ref to `a`
gcc -Wl,--no-as-needed -fuse-ld=bfd main.c -static -L . -lbar -lfoo # 4. OK

接著我們來解釋發生什麼事, 而開始說明前先說, `--as-needed` 對 static library 沒有任何影響。對於 static library 的行為就是看目前有無 undef symbol, 有的話就去 .a 看有沒有任何一個 .o 有 define, 也就是前面有大大提到的

> 印象中有 undefined symbol 才會去 lib 裡面找不是嘛＠＠

因為 `--as-needed `對 static library 沒差所以我們直接兩兩一組來解釋
* case 1,3
main 有 undef symbol b
掃描到 foo 發現沒人有需要的 symbol, 丟掉掃描到 bar 發現有人有 symbol b, 把 libbar.c.o 拉進來a 因為掃到 foo 的時候還沒人要所以丟掉, 後來要用但來不及了

* case 2,4
main 有 undef symbol b
掃描到 bar 發現有人有 symbol b, 把 libbar.c.o 拉進來
掃描到 foo 發現有人有 symbol a, 把 libfoo.c.o 拉進來
Done!

看到這邊一定覺得超靠北的為什麼順序這麼麻煩有沒有一勞永逸的方法, 答案是有ㄛ, library 通通用 `-Wl,--start-group` 跟 `-Wl,--end-group` 包起來就可以不論 `static/dynamic`, `as-needed/no-as-needed` 通通都不用管順序了呢!喔不過前面提到因為效能的考量因為這東西就是要用比較長的 link time 去換來的,所以這個行為不是預設的

gcc -Wl,--as-needed -fuse-ld=bfd main.c -static -L . -Wl,--start-group -lfoo -lbar -Wl,--end-group
gcc -Wl,--as-needed -fuse-ld=bfd main.c -static -L . -Wl,--start-group -lbar -lfoo -Wl,--end-group
gcc -Wl,--no-as-needed -fuse-ld=bfd main.c -static -L . -Wl,--start-group -lfoo -lbar -Wl,--end-group
gcc -Wl,--no-as-needed -fuse-ld=bfd main.c -static -L . -Wl,--start-group -lbar -lfoo -Wl,--end-group
gcc -Wl,--as-needed -fuse-ld=bfd main.c -L . -Wl,--start-group -lfoo -lbar -Wl,--end-group
gcc -Wl,--as-needed -fuse-ld=bfd main.c -L . -Wl,--start-group -lbar -lfoo -Wl,--end-group
gcc -Wl,--no-as-needed -fuse-ld=bfd main.c -L . -Wl,--start-group -lfoo -lbar -Wl,--end-group
gcc -Wl,--no-as-needed -fuse-ld=bfd main.c -L . -Wl,--start-group -lbar -lfoo -Wl,--end-group

那最後回到最開始的問題, 為啥 `gcc` 要 link 那麼多次又要下 `-push-state`, `-as-needed`, `pop-state`, 因為 compiler 不知道底下 linker 的行為是啥以及 input library 是 static or shared, 所以就通通用保守的方式來弄啦~

最後再次聲明, 我不是 linker 專家, 有錯或描述奇怪的地方請不吝指出
打完後發現應該要 blog 才對...XD