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 發生衝突，我們可以將 Selector 新增至 Hypothesize，以避免衝突：

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

我們會更新 FIDL API 大綱，建議您在 Selector 的方法名稱中加上「_」來解決衝突問題。fidlc 也會建議這項修正方式。

請注意，每個介面只需要有一個序數，這點與手動指定的序數類似。如果我們希望序數在所有介面中皆不重複，則應在其他 FTP 中提出。

經過簡單的計算，在介面上使用 31 位元和 100 個方法時，發生衝突的機率為 .0003%，因此我們預期雜湊衝突的機率極低。

選取器 Bikeshed

Selector 的其他建議：

• WireName (abarth)
• OriginalName (ctiller)
• Salt (abarth；稍有不同，因為它建議新增編譯器指定的鹽值，而非其他名稱)
• OrdinalName

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

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

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

零序數

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

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

• 任何這類演算法都不會明顯可見，
• 零個案例的情況極為罕見，

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

活動

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

編譯器和繫結異動

我們認為，只有 fidlc 需要修改，才能支援序數雜湊；程式碼產生後端則不需要修改。這是因為 fidlc 會計算序數，並將其以 JSON IR 格式傳送至後端。

綁定項目不需要變更。

導入策略

我們預計以不同的階段實施這項功能：

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

以上是軟轉換；變更 fidlc 以使用雜湊序數 (步驟 4b) 不應中斷滾動器，因為滾動器是根據整個樹狀結構的單一版本建構。

在 jeremymanson@google.com 實作這個 FTP 時，他選擇以手動指定的序數優先於雜湊序數，這與上述步驟 4b 不同。這樣一來，所有使用手動指定的序數 ABI 相容的現有介面，只會在未指定序數時使用雜湊序數。

人體工學

優點：

• 寫入介面應更簡單。

缺點：

• 程式設計師需要瞭解新的屬性 Selector，這個屬性有兩個用途：重新命名和衝突解決。
• 變更方法名稱會破壞 ABI 相容性，但這點可能不明顯，而程式設計師指定的序數則不受影響。使用者教育訓練 (例如提供更完善的文件) 可以改善這個問題。
  • 請注意，其他元件系統 (例如 COM 和 Objective-C) 通常也會在重新命名介面方法時破壞 ABI 相容性。因此，使用過類似系統的開發人員可能會對這項行為感到熟悉。
• 在某些不尋常的情況下，例如在同一個 Zircon 管道上使用多個 FIDL 介面，如果失去對序號的手動控制權，可能會導致偵錯功能降低。

請注意，作者主要是基於人體工學考量而開發這項 FTP。

說明文件和範例

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

回溯相容性

• 設計上，雜湊序數與手動指定的序數不相容。我們認為這不是問題，因為
  • fidlc 變更為二進位 (會使用雜湊或手動序號)，
  • 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++ 虛擬資料表來進行程序內呼叫，因此需要 ABI 和編譯器支援，才能支援方法調度。apang@google.com 建議為 ctiller@google.com 的 Phickle 提案中的表格使用序號雜湊。ianloic@google.com 和 apang@google.com 在 2018/10/18 (星期四) 會面討論這個問題。