RFC-0029：增加方法一般

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

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

編輯此 RFC

編輯 RFC 中繼資料

摘要

我們建議：

  1. 如要將方法序數的大小提高到 64 位元 (上限為 32 位元)， 同時保有 Fuchsia 的最高順序位元範圍 預留用量；
  2. 將 Pepitaph Ordinal 更新為 0xFFFFFFFFFFFFFFFF (從 0xFFFFFFFF)；
  3. 透過使用 交易標頭；
  4. 並停止使用 [FragileBase] 屬性。

與其他 RFC 的關係

這個 RFC 已由以下機構取代：

提振精神

遠處防衛音樂

我們調查過遠處發生故障問題的時間， 就會介紹組合模型

簡單來說，當 Child 通訊協定組成 Parent 通訊協定時， Parent 是否可能在事後 以 Child 中定義的方法運作。 在沒有發現服務中斷情形的情況下，這項變更可能會在 Parent 中進行 造成「遠距離」在 Child 通訊協定中公開 IP 位址

以我們目前的序數雜湊架構來說，約有 2 類 可能會在 1,000 個方法順序下，導致通訊協定發生衝突。 這很有可能是通訊協定數量龐大 (而且是預期的 通訊協定)，並在 FIDL 中呈現。 我們已改用臨時註解 [FragileBase] 來表示這 並通知開發人員注意這個問題。

增加方法序數專用的位元數 如預期發生這個問題，導致特定程度的衝突可能性 但在實際層面而言，發生故障的機率。

方法序數

通用的生日問題可以充分描述可能性 碰撞力道 我們有 D = 2^k 項可能 (「天」)，正在尋求機會 在「N」方法 (「People」) 之間，其中兩種方法剛好碰撞 (「生日相同」)。

如果將門檻設為 100 萬次 我們願意接受的碰撞機率，最終會達到 可以：

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

就上述例子而言，47 位元以上為合理的選擇。 我們選擇 63 位元的原因如下：

  • 實務上，採用 JSON 標準格式 剖析器 (例如 Go 中的 Python)。 (在 JSON IR 的 v2 中，我們打算將泛型包裝為字串)。
  • 這裡有空間可播放控制訊息，還有空間加入其他標幟 因為這類資源之後需要分配 今天，目前唯一的控制訊息是口號。

我們會為保留的序增加一些位元，因此兩者的結果大小 必須是 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

將雜湊納入標頭

交易郵件標頭現在包含四個位元組欄位： 交易 ID、預留項目、旗標和目前序數 保留欄位將用於 Epitaph 的錯誤代碼。 因此，我們提議將序數欄位從 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
}

兩者皆「取得」方法的 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)))