RFC-0020：介面序數雜湊

「60% 的時間，這都是面試問題的答案」

摘要

我們建議移除程式設計師手動指定介面方法序數 ¹ 的功能。編譯器會根據完整方法名稱 (即程式庫名稱、介面名稱和方法名稱) 的雜湊值產生序數。方法重新命名後，會透過新的 Selector 屬性與 ABI 相容 (請參閱下文)。

我們特別限制這個 FTP，僅適用於介面的序數雜湊提案，不適用於列舉、表格或可擴充的聯集。我們認為這些結構的用途差異夠大，因此需要進一步調查，並採用不同的 FTP。

範例

目前 FIDL 作者會撰寫：

library foo;

interface Science {
    1: Hypothesize();
    2: Investigate();
    3: Explode();
    4: Reproduce();
};

這個 FTP 會啟用序數索引的捨棄功能：

interface Science {
    Hypothesize();  // look, no ordinals!
    Investigate();
    Explode();
    Reproduce();
};

在幕後，編譯器實際上會產生類似這樣的序數：

interface Science {
    // ordinal = SHA-256 of the fully-qualified method name,
    // i.e. "foo.Science/MethodName", truncated to 32 bits
    0xf0b6ede8: Hypothesize();
    0x1c50e6df: Investigate();
    0xff408f25: Explode();
    0x0c2a400e: Reproduce();
};

提振精神

• 手動指定序數大多是機械式作業。 如果不需要考慮介面，撰寫介面會比較輕鬆。
• 如果使用良好的雜湊，雜湊不太可能導致序數衝突，這比人工手動編寫序數更有效率 (特別是使用介面繼承時)。詳情請參閱下方的序數衝突一節。
• 程式設計師目前必須確保不同方法的序數不會衝突。如果介面的方法不多，這很容易做到，但如果介面有很多方法，這就會變得不簡單。序數編號有不同的程式設計風格和學派，因此程式設計風格不一致。
  • 大多數介面都是從 1 開始，然後向上遞增。
  • 不過，有些作者偏好將不同介面方法分組到範圍中 (例如 1-10、100-110 等)。
  • 移除手動編號的序數後，系統也會移除不一致的樣式，作者不必再決定要使用哪種樣式。
• 介面繼承可能會導致序數意外衝突。目前已嘗試解決這個問題兩次：
  • FTP-010 (已拒絕) 提議使用 OrdinalRange 屬性，讓介面繼承行為更具可預測性，但遭到拒絕。
  • FragileBase ² 是目前的暫時解決方案，但無法解決確保序號不會衝突的核心問題。
  • 如果序數經過雜湊處理，且介面和程式庫名稱用於計算雜湊，雜湊處理序數就不會導致序數衝突，進而解決介面繼承問題 (極為罕見的雜湊衝突除外)。

設計

雜湊

雜湊序數是透過下列項目的 SHA-256 雜湊值衍生而來：

library name (encoded as UTF-8; no trailing \0)
".", ASCII 0x2e
interface name (encoded as UTF-8; no trailing \0)
"/", ASCII 0x2f
method name (encoded as UTF-8; no trailing \0)

舉例來說，下列 FIDL 宣告：

library foo;

interface Science {
    Hypothesize();
    Investigate();
    Explode();
    Reproduce();
};

會使用下列位元組模式計算序數雜湊：

foo.Science/Hypothesize
foo.Science/Investigate
foo.Science/Explode
foo.Science/Reproduce

由於 fidlc 已輸出這個格式的完整方法名稱 (請參閱 fidlc 的 NameName() 方法)，因此使用 . 和 / 分隔符。

計算出 SHA-256 雜湊後，請按照下列步驟操作：

1. 擷取 SHA-256 雜湊的前 32 位元 (例如 echo -n foo.Science.Hypothesize | shasum -a 256 | head -c8)
2. 上位元設為 0，產生有效的 31 位元雜湊值，並以零填補至 32 位元。(由於 FIDL 傳輸格式會保留 32 位元序數中的最高有效位元，因此使用 31 位元)。

虛擬程式碼：

full_hash = sha256(library_name + "." + interface_name + "/" + method_name)
ordinal = full_hash[0] |
        full_hash[1] << 8 |
        full_hash[2] << 16 |
        full_hash[3] << 24;
ordinal &= 0x7fffffff;

選取器屬性和方法重新命名

我們定義了 Selector 屬性，編譯器會使用這個屬性計算雜湊序數，而不是使用方法名稱。如果方法名稱沒有 Selector 屬性，系統會將方法名稱做為 Selector。(介面和程式庫名稱仍會用於雜湊計算)。

Selector 可用來重新命名方法，且不會破壞 ABI 相容性，這是手動指定序數的優點之一。舉例來說，如果我們想在 Science 介面中將 Investigate 方法重新命名為 Experiment，可以編寫：

interface Science {
    [Selector="Investigate"] Experiment();
};

我們只允許方法使用 Selector 屬性。重新命名程式庫的情況較為少見，因此在這種情況下，我們不會優先保留 ABI 相容性。重新命名介面時也是如此。此外，重新命名的介面與 Discoverable 屬性的互動會造成混淆：哪個名稱可供探索？

序數衝突與解決

如果雜湊序數與同一介面中的另一個雜湊序數發生衝突，編譯器會發出錯誤，並依賴人工指定 Selector 屬性來解決衝突 ³。

舉例來說，如果方法名稱 Hypothesize 與方法名稱 Investigate 衝突，我們可以在 Hypothesize 中加入 Selector，避免發生衝突：

interface Science {
    [Selector="Hypothesize_"] Hypothesize();
    Investigate();  // should no longer conflict with Hypothesize_
};

我們會更新 FIDL API 評分標準，建議在 Selector 的方法名稱中附加「_」，以解決衝突。fidlc也會建議修正這個問題。

請注意，序數只需要在每個介面中保持不重複，與手動指定的序數類似。如果我們希望序數在所有介面中都是唯一的，則應在另一個 FTP 中提出建議。

根據粗略計算，如果介面上有 31 位元和 100 個方法，發生衝突的機率為 0.0003%，因此我們預期雜湊衝突極為罕見。

Selector Bikeshed

「Selector」的其他建議：

• WireName (abarth)
• OriginalName (ctiller)
• Salt (abarth；略有不同，因為建議新增編譯器指定的鹽，而不是替代名稱)
• OrdinalName

我們選擇 Selector，因為我們認為這個名稱比 WireName 或 OriginalName 更能反映屬性的意圖。

我們選擇讓程式設計師指定序數名稱，而非序數索引，原因如下：

• 要求索引會更加繁瑣 (例如，發生衝突時複製並貼上原始 SHA-256 雜湊值)，
• 指定序數名稱可啟用 ABI 相容的方法重新命名，且
• 指定名稱而非索引，可讓程式設計師在編寫介面時，維持相同的抽象層級，不必降低抽象層級，思考序數。

零序數

零是無效的序數。如果方法名稱雜湊為零，編譯器會將其視為雜湊衝突，並要求使用者指定雜湊不為零的 Selector。

我們曾考慮讓 fidlc 透過確定性轉換自動重新雜湊名稱，但認為：

• 任何這類演算法都不會顯而易見，且
• 零的情況極為罕見，

因此，這種做法不值得讓人體工學和編譯器實作變得複雜。

活動

這個 FTP 也涵蓋事件，FIDL 語言文件 ⁴ 將事件視為方法的子集。

編譯器和繫結異動

我們認為只需要修改 fidlc 即可支援序數雜湊，程式碼產生後端不需要修改。這是因為 fidlc 會計算序數，並將序數發布至後端的 JSON IR。

繫結不需要變更。

導入策略

我們打算分階段導入這項功能：

1. 在 fidlc 中新增程式碼，以計算雜湊。
2. 為程式庫新增屬性支援。
3. 向 Fuchsia 工程團隊廣播變更意圖，讓他們瞭解潛在問題。 a. 建議在特定日期淘汰手動序數，屆時我們預期會完成下一個步驟。
4. 在同一個 CL 中： a. 修改 FIDL 文法的介面方法規則，將序數設為選用；詳情請參閱下文。 b. 忽略手動指定的序數，並使用雜湊序數做為傳遞至程式碼產生後端的序數名稱。 c. 手動新增 Selector 屬性，修正所有現有的雜湊值衝突。
5. 測試變更兩週，確保沒有任何生產問題。 a. 這段時間內編寫的新 FIDL 介面不應使用序數。 b. 手動序數視為已淘汰，但 fidlc 不會發出相關警告。與團隊合作，確保介面中沒有手動指定的序數。兩週後，更新 FIDL 格式化工具，移除序數，並大量套用至整個 Fuchsia 樹狀結構。
6. 停止支援手動指定的序數。

上述是軟性轉移；變更 fidlc 以使用雜湊序數 (步驟 4b) 不應中斷捲動器，因為捲動器是從整個樹狀結構的單一版本建構而來。

在 jeremymanson@google.com 實作這個 FTP 時，他選擇偏好手動指定的序數，而非雜湊序數，這與上述步驟 4b 不同。這樣一來，所有使用手動指定序數的現有介面都會保持 ABI 相容性，且只會在未指定序數時使用雜湊序數。

人體工學

優點：

• 撰寫介面應更簡單。

缺點：

• 程式設計師必須瞭解新的 Selector 屬性，這個屬性有兩個用途：重新命名和解決衝突。
• 變更方法名稱可能會導致 ABI 不相容，但程式設計師指定的序數不會發生這種情況，因此可能不明顯。使用者教育 (例如更完善的文件) 可以改善這種情況。
  • 請注意，如果介面方法重新命名，COM 和 Objective-C 等其他元件系統通常也會中斷 ABI 相容性。因此，使用過類似系統的開發人員可能對這種行為很熟悉。
• 如果無法手動控制序數，在異常情況下 (例如在同一個 Zircon 管道上使用多個 FIDL 介面)，可能較難進行偵錯。

請注意，作者主要是基於人體工學考量，才提出這項 FTP。

說明文件和範例

我們預計會變更 FIDL 屬性、文法、語言和線路格式文件。如Selector一節所述，API 可讀性評量標準文件也應更新。

回溯相容性

• 根據設計，雜湊序數與手動指定的序數在 ABI 中不相容。我們預期這不會造成問題，因為
  • fidlc 變更為二進位 (系統會使用雜湊的 XOR 或手動序數)，且
  • fidlc 用於建構整個樹狀結構，因此
  • 樹狀結構的所有部分都會持續使用所選的序數配置。
• 雜湊序數與 API (來源) 相容。 現有來源檔案會保持相容性；手動序數將遭到淘汰 (請參閱「實作策略」)。
• 如果使用兩個不同的 fidlc 建構版本 (也就是兩個不同的平台來源樹狀結構建構版本)，且 FIDL 介面用於跨機器通訊，就會發生錯誤。作者目前並未發現有任何用途，因此這應該不是問題。

效能

我們預期 fidlc 的速度只會略為變慢，因為現在必須對介面中的所有方法名稱進行雜湊處理，才能計算這些名稱。

我們預期對執行階段效能的影響微乎其微。 編譯器可能已為先前小而連續的手動指定序數產生跳轉表，但使用雜湊序數時，這些序數會透過稀疏序數空間進行二元搜尋。同樣的機制也可能對二進位檔大小造成微不足道的影響。 (表單驅動的調度作業可能會改善大小和速度問題。)

安全性

我們預期不會發生執行階段安全問題，因為序數雜湊沒有執行階段變更，只會變更透過網路傳送的序數值。

使用加密雜湊 (SHA-256) 可能會讓某些人認為雜湊需要具備強大的加密功能；我們認為這不會造成安全問題，因為：

• FIDL 編譯器會在編譯時檢查雜湊值衝突，並要求人工輸入來解決問題，以及
• 我們使用 SHA-256 並非為了加密，而是因為我們需要極不可能發生衝突的雜湊。CRC-32 (甚至是 strlen()) 也適用，但可能會導致更多衝突，這只是不方便而已。

SHA-256 雜湊值的截斷作業也可能讓部分使用者感到憂慮，但我們同樣認為不會有安全性問題，因為 FIDL 編譯器會靜態檢查雜湊值衝突 ⁵。

測試

ianloic@google.com 已分析現有的 FIDL 介面，並判斷沒有任何雜湊值衝突。

我們會仔細考量如何測試實際的雜湊值衝突案例，因為以良好的雜湊值人為產生雜湊值衝突很困難 (這是設計使然)。

否則，只要進行單元測試、CQ 測試、相容性測試和手動測試，即可確保序數雜湊功能穩定運作。

缺點、替代方案和未知事項

這項 FTP 刻意只處理介面的序數雜湊。不會針對列舉、表格或可擴充聯集的手動列舉序數提出變更建議。

jeffbrown@google.com 建議使用完美雜湊，並已納入考量。 FTP 作者不太熟悉完美雜湊配置，但認為隨著時間推移，新增額外方法會變更現有方法的雜湊，因此會破壞 ABI 相容性，導致完美雜湊不適用。動態完美雜湊可能可行，但會引發雜湊變更的相同問題，而且與標準雜湊相比，動態完美雜湊較不為人所知，也更複雜，因此不值得進一步調查。

如要移除手動序數，另一種做法是透過網路傳送完整的方法名稱，許多 (大多數？) 其他 RPC 系統都採用這種做法 (請參閱下方的參考資料)。這會對執行階段效能造成影響，可能與 FIDL 的預期用途衝突。

我們考慮過指定所用雜湊，以便日後變更， 如果 SHA-256 最終出現問題，而其他雜湊可以解決。 這種設計在安全應用程式中很常見，因為廣泛使用的密碼編譯雜湊日後可能會發現安全漏洞。不過，指定雜湊值可能需要變更連線格式，且所有語言繫結都必須實作程式碼來選取雜湊演算法，這會大幅增加編譯器和繫結程式碼的複雜度。我們認為這種取捨並不值得。 我們瞭解 git 也曾對 SHA-1 採取這種態度，現在則有些後悔當初的決定，但我們認為我們的用途與他們不同，因此有理由將雜湊演算法硬式編碼。

探索

• 如果能以節省空間的方式識別方法，就能有效表示方法，讓方法成為一級物件。
  • 舉例來說，這可讓方法做為 FIDL 呼叫中的引數，或讓 FIDL 方法傳回另一個方法做為結果。可以說，目前已有這類用途，方法會傳回具有單一方法做為實際方法傳回值的介面。
• 建議的 31 位元雜湊可擴充為 64/128/53 位元； SHA-256 提供大量位元。
• 將 ordinal 重新命名為 selector，這是現有的概念，在其他語言和元件系統中具有相同用途。
• 方法名稱和介面名稱可能有所不同，因此我們有兩組不同的資料。這樣一來，介面名稱和方法名稱就會是專屬名稱。我們可能需要超過 32 位元。
• 如上所述，列舉、表格和可擴充聯集不在範圍內。 不過，我們認為這項 FTP 可能適用於他們。 初步想法：
  • 我們不確定列舉是否需要這項功能。 簡單且標準化的連續整數編號似乎就足夠了。
  • 這可能可以直接套用至可擴充的聯集。
  • 由於序數目前必須連續，才能採用封裝表示法，因此表格需要不同的線路格式才能採用序數雜湊。
• FIDL 目前保留了序數的上層位元，並在文件中明確指出，上層位元的範圍預計會用於控制流程等。作者認為，這可能是序數衝突的原因之一。我們是否要重新審查這項政策？
  • 將序數空間擴展至 64 位元 (如上所述)，大致上就能解決這個問題。
  • abarth@google.com建議在 Fuchsia IPC 聊天室中預留，僅保留 0xFFFFxxxx。
• 我們可以在計算出的雜湊中加入方法的引數型別，如果日後需要，這會支援方法多載。
  • jeffbrown@google.com 提到，完整方法簽章的雜湊可能會限制介面擴充的機會，且多種程式設計語言的對應會造成多載地圖不佳。
• 由於序數雜湊應可解決使用介面繼承時的序數衝突，因此也可以移除 FragileBase 屬性。
  • 程式碼搜尋顯示 FragileBase 的使用次數約為 9 次。
• 作者擔心，如果許多方法都有 Selector 屬性，隨著時間演進，介面可能會變得難以閱讀。
  • 解決這個問題的方法之一，是採用類似 Objective-C 類別或 C# 部分類別的機制，也就是「擴充」現有的已宣告介面，以便在個別宣告中新增屬性。

既有技術和參考資料

有趣的是，我們不知道有任何其他方法分派或 RPC 系統會使用方法名稱的雜湊值，來識別要呼叫的方法。

大多數 RPC 系統會依名稱呼叫方法 (例如 gRPC/Protobuf 服務、Thrift、D-Bus)。對於程序內方法呼叫，Objective-C 會使用保證不重複的 char* 指標值 (稱為選取器)，識別應在類別中呼叫的方法。Objective-C 執行階段可將選取器對應至字串化方法名稱，反之亦然。如果是程序外方法呼叫，Objective-C 分散式物件會使用方法名稱進行叫用。COM 會直接使用 C++ vtable 進行程序內呼叫，因此需要 ABI 和編譯器支援，才能支援方法調度。apang@google.com 建議在 ctiller@google.com 的 Phickle 提案中，對表格使用序數雜湊。ianloic@google.com 和 apang@google.com 於 2018 年 10 月 18 日星期四會面，討論這個問題。