RFC-0029：增加方法一般

RFC-0029：遞增方法序數
狀態已接受
區域
  • FIDL
說明

將方法序數的大小增加到 64 位元 (最多 32 位元)，同時維持為 Fuchsia 保留用量設定的最高順序位元範圍。將 Epitaph 序語更新為 0xFFFFFFFFFFFFFFFF (從 0xFFFFFFFF)。使用交易標頭的旗標欄位來封裝增加的序數大小。並停用 FragileBase 屬性。
作者
提交日期 (年/月)2019-02-14
審查日期 (年/月)2019-02-28

編輯此 RFC

編輯 RFC 中繼資料

摘要

我們建議：

  1. 如要將方法序數的大小增加到 64 位元 (從 32 位元)，同時為 Fuchsia 保留用量設定最高順序位元的範圍，即可；
  2. 將劇集序數更新為 0xFFFFFFFFFFFFFFFF (從 0xFFFFFFFF)；
  3. 透過使用交易標頭的旗標欄位來封裝增加的序數大小；
  4. 並停止使用 [FragileBase] 屬性。

與其他 RFC 的關係

這個 RFC 已由以下因素取代：

提振精神

遠方的打擊中斷

我們查看了一段時間的中斷問題，而該問題是由組合模型所導入。

簡單來說，當 Child 通訊協定組成 Parent 通訊協定時，Parent 可能會在不符合 Child 中定義的方法後導入方法。這項變更可能會在 Parent 中完成，但未知會中斷 Child 通訊協定中造成的中斷情形。

根據我們目前的序數雜湊配置，大約有 2 倍之多可能以 1,000 個方法的順序造成通訊協定發生衝突。這很可能是在 FIDL 中建構及表示的大量通訊協定 (以及預期的通訊協定)。我們已改用臨時註解 [FragileBase] 來指出這個問題，並讓開發人員知道這個問題。

透過增加方法序數專用的位元數量，即可降低碰撞到關卡滿足程度期望的可能性，進而在不存在的距離 (實際做法) 下考慮這個問題的故障情形。

方法序數的大小

「一般化的生日問題」可用來描述衝突機率。我們有 D = 2^k 的可能性 (「天」)，因此希望在 N 個方法 (「人」) 中，這兩種方法可能產生衝突 (「相同生日」)。

如果我們將門檻設在一百萬

  • 31 位元：約 60 位元
  • 39 位元：約 1k
  • 47 位元：約 16K
  • 52 位元：約 95k
  • 63 位元：約 430 萬

根據上述資料，47 位元以上是合理的選擇。我們選擇 63 位元的其他因素包括：

  • 在實務上，使用標準剖析器 (例如 in Go 或 Python) 使用 JSON 格式表示序數可以安全。(在 JSON IR 的第 2 版中，我們打算將序數包裝為字串。)
  • 剩餘的空間可用來存放控制訊息，還有空間供其他旗標使用。如今，目前唯一的控制訊息是 Epitaph。

我們為保留的序數加入較高的位元，因此序數產生的結果大小為 64 位元。

我們視為限制在 52 位元 (處理控制訊息總計為 53 位元)，因為這是 IEEE754 中代表的最大正整數，這有利於在僅支援雙倍數的語言 (例如JavaScript)。但是，這些語言仍需操縱序數，並將這些語言置於線上，因此需要進一步的機制，才能存取構成雙重的個別位元組。

設計

雜湊計算

RFC-0020：介面序數雜湊中導入的雜湊計算方法略有修改。這樣應該都會產生 64 位元編號，且用於計算雜湊的字串為 <library>/<top level declaration>.<member> (根據 RFC-0043：文件註解格式)。

雜湊序數是由以下 SHA-256 雜湊衍生而來：

  • library name：以 UTF-8 編碼；不含結尾的 \0
  • 「/」— 正斜線字元，ASCII 0x2f
  • 通訊協定名稱：採用 UTF-8 編碼，結尾無 \0
  • "." — 句號字元，ASCII 0x2e
  • 方法名稱：採用 UTF-8 編碼；結尾無 \0

以下列 FIDL 宣告為例：

library foo;

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

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

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

計算 SHA-256 雜湊後，會擷取 SHA-256 雜湊的上 63 位元。我們只擷取 63 位元，因為第 64 位元保留系統用途。

虛擬程式碼：

full_hash = sha256(library_name + "/" +
                   protocol_name + "." +
                   method_name)
ordinal = full_hash[0]       |
          full_hash[1] << 8  |
          full_hash[2] << 16 |
          full_hash[3] << 24 |
          full_hash[4] << 32 |
          full_hash[5] << 40 |
          full_hash[6] << 48 |
          full_hash[7] << 56;
ordinal &= 0x7fff ffff ffff ffff; // i.e., 63 ones

標頭中的包裝雜湊

交易訊息標頭目前包含四個 4 個位元組欄位：交易 ID、保留、標記，以及目前的序數。保留欄位會由 Eepitaph 的錯誤代碼使用。 因此，我們提議使用標記欄位 (今天未使用)，將序數欄位從 4 個位元組增加到 8 個位元組。

這個標頭的新定義如下：

  • zx_txid_t txid，交易 ID (32 位元)
    • 具有高位元組合的 txid 已保留供 zx_channel_call() 使用
    • 未設定高位元的 txid 已保留供使用者空間使用
    • 如要進一步瞭解 txid 分配，請參閱 zx_channel_call() 的說明
  • uint32 reserved0，保留供日後使用。
  • uint64 ordinal
    • 零序數無效。
    • 系統已保留 0xfffffffffffff 以上的序數。

JSON IR

沒有變更，且考量到開發人員定義的序數上限為 52 位元，且標準 JSON 剖析器可將這個值剖析為 64 位元浮點數，且精確度不會降低。

其他序數

我們在表格中有序數和可擴充的聯集。我們都不建議您變更這些做法：在這兩種情況下，目前距離不會發生中斷 (例如，可擴充的聯集聯集組合其他可擴充的聯集)。

導入策略

與之前針對明確雜湊序數採取的策略類似。

人體工學

沒有變更

說明文件與範例

需要修改線路格式。

回溯相容性

與舊版相容。

效能

預期不會產生任何影響。 方法和事件分派作業現在必須在 64 位元整數 (而非 32 位元整數) 上完成，預期沒有任何差異。

安全性

不會對安全性造成影響。請參閱「替代做法：識別通訊協定和方法」一文，瞭解安全性是否有利相關用途，且這些用途可透過其他配置提升效能。

測試

序數計算的單元測試。遵循與 RFC-0020：介面序數雜湊類似的格式。

替代做法：識別通訊協定和方法

我們會期望使用沙箱服務來保護另一項服務，避免未經授權的使用行為，也就是某種 FIDL 訊息的防火牆。 建構這類沙箱服務時，有效率地參照一組訊息 (「允許的訊息」) 會很有幫助。有人可以想像一下，使用通訊協定來定義這組訊息。

在這種情況下，有兩個 ID 是非常實用的做法，一個用於通訊協定，另一個用於方法。相較之下，上述的配置方式只會提供一個 ID。

一起來看看這個替代方案，因為：

  • P 位元 (用於通訊協定名稱雜湊)
  • M 位元 (用於方法名稱的雜湊)

因此，序數的總大小如下：

  • P + M + 1 鍵

因為我們需要保留 1 位元的數值供系統序數使用。

舉例來說，使用範例程式庫：

library alternative;

protocol Parent {
    Get(); // alternative/Parent.Get
}

protocol Child {
    compose Parent;
    Get(); // alternative/Child.Get
}

兩個「Get」方法都有相同的 M 位元 (此為「Get」的雜湊)。 不過，P 位元會有所不同，其中一個則是 alternative/Parent 的雜湊，另一個則是 alternative/Child 的雜湊。

從可行性的角度來看，使用與上述類似的數值方法相比，我們：

  • 我們預期需要多少通訊協定？以 10 萬為單位的順序合理。
    • → 需要 P = 52 位元
  • 我們預期可以使用幾種方法？以 1k 的順序合理。
    • → 需要 M = 39 位元
  • 這個配置需要 92 位元

因此，我們認為這是可行的替代方案。

此外，考量進一步的沙箱用途，因為通訊協定組合的關係，無法比對單一通訊協定 ID (方法可能來自多個來源通訊協定)。因此，雖然單一 ID 可能有利於最佳化路徑，但一般而言，在一般情況下，需要查詢某些資料結構才能達到這個效率。

附加條款：碰撞機率

成果

size | num_methods | r | p(collision)
-----+-------------+---+-------------
  31 |        1000 |   | 0.0002325707643
  39 |        1000 | x | 0.0000009085847943
  47 |        1000 | x | 0.000000003549160959
  52 |        1000 | x | 0.0000000001109112802
  63 |        1000 | x | 0.00000000000005415589852
  31 |       10000 |   | 0.02301183054
  39 |       10000 |   | 0.00009093624028
  47 |       10000 | x | 0.0000003552357776
  52 |       10000 | x | 0.00000001110111996
  63 |       10000 | x | 0.000000000005420468761
  31 |       50000 |   | 0.4412566126
  39 |       50000 |   | 0.002271108402
  47 |       50000 |   | 0.00000888156712
  52 |       50000 | x | 0.0000002775501665
  63 |       50000 | x | 0.000000000135522561
  31 |      100000 |   | 0.9025370676
  39 |      100000 |   | 0.009053622963
  47 |      100000 |   | 0.00003552615045
  52 |      100000 |   | 0.000001110211306
  63 |      100000 | x | 0.0000000005420956651
  31 |     1000000 |   | 1.0
  39 |     1000000 |   | 0.5972719635
  47 |     1000000 |   | 0.003546406718
  52 |     1000000 |   | 0.0001110160287
  63 |     1000000 | x | 0.00000005421005294

size: max. num_methods
31: 66
39: 1049
47: 16777
52: 94906
63: 4294968

程式碼

使用 http://mpmath.org 計算各種機率。

from mpmath import mp
mp.dps = 50
mp.pretty = True

# Given n random integers drawn from a discrete uniform distribution with
# range [1,d], what is the probability p(n; d) that at least two numbers are
# the same?
def p_collision(n, d):
    # 1 - ((d - 1) / d) ^ (n * (n - 1) / 2)
    base = mp.fdiv(mp.fsub(d, 1), d)
    expo = mp.fdiv(mp.fmul(n, mp.fsub(n, 1)), 2)
    return mp.fsub(1, mp.power(base, expo))

print("size | num_methods | r | p(collision)")
for num_methods in [1000, 10000, 50000, 100000, 1000000]:
    print("-----+-------------+---+-------------")
    for size in [31, 39, 47, 52, 63]:
        p = p_collision(num_methods, mp.power(2, size))
        # 1 in 1,000,000
        result = " "
        if p < mp.fdiv(1, 1000000):
            result = "x"
        print("%4d | %11d | %s | %s" % (size, num_methods, result, mp.nstr(p, 10, min_fixed = -mp.inf)))

def find_max_num_methods(size):
    low = 1
    target = 1
    upper = 10000000
    while True:
        p = p_collision(target, mp.power(2, size))
        if p < mp.fdiv(1, 1000000):
            low = target
        else:
            upper = target
        target = ((upper - low) / 2) + low
        if upper - low < 2:
            return low

print("size: max. num_methods")
for size in [31, 39, 47, 52, 63]:
    print("%d: %s" % (size, find_max_num_methods(size)))