Re: [問題] 請益一段程式碼 (offsetof/container_of)

[LPH66 (-6.2598534e+18f)]

昨天晚上各種原因早早躺床了所以到現在才來回...

順便改個標題給以後搜尋

※ 引述《j5128709 (j5128709)》之銘言：
: /*##### 程式碼 #####*/
: do
: {
:         dlink_t *entry;
:         for ( (entry) = (&idle_1)->head.next;
:               (entry) != &(&idle_1)->head;
:               (entry) = (entry)->next;
:             ) {
:    u_idle_t *idle = ( (u_idle_t*) ((u8 *) (entry) -
:                     (u8 *) (&((u_idle_t *)  0)->link )));  //Q1
:         idle->idle();
:         } //end for
: }while(0);
: 想問說 Q1 這行的該如何解釋? 這"0"是說位址嘛?
: 還是說有啥特別用意??
: 感謝各位前輩看完
原 PO 後來有丟水球給我說原始的 macro 是這一個:

#ifndef container_of
#   define container_of(address, type, field) \
       ( (type *) ((u8 *) (address) - (u8 *) (&((type *) 0)->field )))

這個 macro 其實在 linux kernel 裡滿常見的, 它算是 offsetof 的逆向版

這裡先講一下什麼是 offsetof:

offsetof 是標準中有定義的 macro (在 <stddef.h> 裡)

offsetof(type, member) 之作用為:

    給定一個結構 type, 及其成員名 member,

    求此 member 在這 type 裡的偏移位元組量

(C++ 在這裡有些規定, 不過這裡先不管, 先講 C 的部份)

所謂的偏移位元組量就是在底層資料結構當中

這個成員是放在整個結構的什麼地方, 相對於結構開頭移了多少位元組

一般來說, offsetof 在 C 的實作會是如此:

#define offsetof(type, member) (size_t)&(((type*)0)->member)

(這裡跟這個 0 有關的東西等下會提)

可以看到這個定義跟原 PO 問的 macro 的後半段幾乎一樣

這裡就要回頭講原 PO 問的 container_of 了

這個 macro 不是標準定義, 而是在 linux kernel 出現過

在那之中的定義是這樣子的:

#define container_of(ptr, type, member) ({ \
     const typeof( ((type *)0)->member ) *__mptr = (ptr); \
     (type *)( (char *)__mptr - offsetof(type,member) );})

先不看實作細節, 這 container_of 的作用是:

    給定一個結構 type, 其成員名 member,

    及一個已知指向某個 type 結構的 member 成員之指標 ptr,

    求一指標指向此 type 結構

在 linux kernel 裡的基本狀況是某個 struct 裡的成員其指標送去別的地方了

當別的地方送回來這個指標時, 我要求得這指標究竟是哪個 struct 的以進行後續操作

這時就會使用 container_of 來求得之

====

那麼這裡就來講一下這兩個 macro 的實作細節

先講 offsetof, 這裡重貼一下這個常見的實作:

#define offsetof(type, member) (size_t)&(((type*)0)->member)

它做的事其實是這樣的:

           (type*)0             一個型態為 type* 的空指標常數 (#1N8UkD6I)
        &((        )->member)   其指向之 type 結構的 member 成員之指標
(size_t)                        將其轉為 size_t 做為結果

中間的第二步比較好懂, 就只是一個結構指標取出其成員的指標而已

這一步對編譯器來說即是找出我們想求得的偏移值, 加上指標值之後做為結果

於是為了取出這個偏移值, 第一步取用了空指標常數

如果空指標常數也是指向位址 0 的話

那加上偏移值的位址就正好只剩下我們想要的偏移值, 所以轉為 size_t 後即為所求

但是我們知道空指標常數並不一定指向位址 0

因此平常是不允許直接這樣寫的, 只在當環境是確定的時候才可以這麼做

(在一些空指標常數可能不指向位址 0 的環境裡也是有類似這樣的定義存在:

 #define offsetof(s,memb) ((size_t)((char *)&((s *)0)->memb-(char *)0))

 這裡為了補償可能不指向位址 0 的空指標常數

 在取得成員指標後又減去了空指標常數的值, 即是減去結構開頭的位址

 這樣就可以取得想要的偏移值了)

因此這也是為什麼 offsetof 會作為 C 標準裡的一個 macro

就是因為由於各種原因它不可能有可攜實作, 但在各自的環境裡總是有辦法寫得出來

====

接下來是 container_of, 同樣重貼一下 linux kernel 的實作:

#define container_of(ptr, type, member) ({ \
     const typeof( ((type *)0)->member ) *__mptr = (ptr); \
     (type *)( (char *)__mptr - offsetof(type,member) );})

這裡它使用了 gcc 裡的 block expression

({ ... }) 這個東西回傳 { } 裡面最後一個 expression 的結果做為結果

這使我們可以在 { } 裡宣告變數或使用 for/while/switch/等等

這裡就是它宣告了一個變數 __mptr 其型態為

    const typeof( ((type *)0)->member ) *

這個 typeof 也是 gcc 專有, 其效果有點類似 C++ 標準的 decltype

是用來求得其參數的型態

(注意不論是 typeof 或是 decltype 都不是 macro, 其結果是個型態)

這裡用來求型態的式子是 ((type *)0)->member

從上面我們知道了這式子是對一個型態為 type * 的空指標常數求其成員

所以 typeof 的結果就是這個 member 的型態

有趣的是, 這裡並不用擔心剛才提到的空指標常數計算問題

這是因為 typeof 只關心這式子的型態而不關心其值

也就是說 typeof 並不會去實際計算那個式子, 而只會去看看它該產生什麼型態而已

回到 __mptr, 於是這樣這個 __mptr 的型態就很清楚了:

它是一個指向「member 的型態」的指標 (const 在此略去)

有了它之後, 第二行做了這些事:

          (char *)__mptr                                剛才那指標轉成 char*
                         - offsetof(type,member)        減去偏移值
(type *)(                                        )      再轉成 type *

我們知道 char 總是 1 byte, 所以轉成 char * 再減去偏移值即是倒回去求開頭

因此最後再轉成 type * 即是所求了

這裡有個細節要先提:

之所以在這裡先宣告一個正確型態的變數來接

是因為我們不能控制 macro 傳進來的參數的型態

而且有很大的可能這個指標是做為一個通用指標 (void *) 傳去別的地方的

所以在轉回來時得要先轉回正確的型態才能倒回去求

但是把兩行合併在一起的話會太醜, 所以就另外宣告一個變數型態來接

由於 { } 的 scope 的關係, 這個變數只在這裡看得到

編譯器的最佳化足以將這裡的變數使用給消掉而不會實際佔用一個變數空間

====

最後回到原 PO 問的定義:

#ifndef container_of
#   define container_of(address, type, field) \
       ( (type *) ((u8 *) (address) - (u8 *) (&((type *) 0)->field )))

在經過上面的講解之後, 這裡很容易可以看出它把上面的實作做了一點化簡合併起來

由於看起來這裡的使用情境裡 address 的型態永遠是對的 (dlink_t *)

因此它略去了轉回正確的 member 型態的操作

然後它把 offsetof 的實作也合併進來了, 可以看到後半段即是 offsetof

不過這裡有一個大問題: offsetof 的結果的型態搞錯了

第二個 (u8 *) 的轉型應該要是個整數型態才是對的

例如 size_t, ptrdiff_t 或懶一點就 int

這樣指標減整數才會得到指標

不然這裡是指標減指標會得到整數, 再轉回指標有一點操作上的危險性

這應該就是推文 longlongint 在講的怪怪的地方了

====

到此為止都是在講 C 的實作

C++ 由於可以對 operator & 進行重載

offsetof 的那個實作可能會呼叫到重載函式

因此 C++ 的 offsetof 不能使用這個方式實作, 而必須倚賴編譯器提供 builtin

事實上 gcc/g++ 的 offsetof 即是使用 __builtin_offsetof 做為定義

剛才也提到 C++ 的 offsetof 對 type 上有些規定

標準規定它必須是所謂 Standard Layout 的型態

它比 POD 稍微鬆一點, 可以有一些有限度的繼承

但基本上各個成員的位址依然是確定的, 所以才可以使用 offsetof 求得之

至於 container_of, 扣除當中 offsetof 的需求外倒是沒什麼其他要求就是了

====

最後關於我的水晶球 (!)

原 PO 貼的那一段程式有好幾個跡象顯示那是 macro 展開之後的結果:

其一, offsetof 一般不會展開來寫

其二, 那個 for 迴圈的 entry 變數有一層括號, 這是 macro 定義的常見狀況

      (見置底十三誡之九)

其三, do...while(0) (見 #1DmPUtv4)

所以與其說是 macro 展開後, 這其實更像是 preprocess 過的程式碼

算上 container_of 這裡大概至少有三條 macro 套在一起...

--
LPH  [acronym]
= Let Program Heal us
                        -- New Uncyclopedian Dictionary, Minmei Publishing Co.

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.39.85
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1462016161.A.1F8.html
推 tuyutd0505: 推水晶球大神好文
推 chuegou: 最後那段水晶球（？）推理  精彩
推 james732: 推水晶球
推 Caesar08: 推
推 j5128709: 推 感謝LPH大 專業的解說!!!
推 oscar60111: 推~~~ 請問這種高級水晶球哪兒買的到呢XD?
※ 編輯: LPH66 (123.195.39.85), 05/01/2016 00:46:50
推 mabinogi805: 高級水晶推理，慧眼穿雲www
推 name2name2: 推
推 Hazukashiine: 推推
推 prismwu: 我們該成立水晶球神教了
推 wtchen: 板工也要水晶球....
→ Frozenmouse: 這水晶球我也想要一個www
推 virve: 團購水晶球？XD
推 VictorTom: 推:)
推 damody: 讚
推 BlazarArc: 推