| RFC-0029：增加方法序號 | |
|---|---|
| 狀態 | 已接受 |
| 區域 |
|
| 說明 | 將方法序號的大小從 32 位元增加至 64 位元，同時保留最高順序位元集合，以便 Fuchsia 保留用途。將墓誌銘序列更新為 0xFFFFFFFFFFFFFFFF (從 0xFFFFFFFF)。使用交易標頭的旗標欄位，將遞增序號大小加以封裝。並停止使用 FragileBase 屬性。 |
| 作者 | |
| 提交日期 (年-月-日) | 2019-02-14 |
| 審查日期 (年-月-日) | 2019-02-28 |
摘要
我們建議：
- 將方法序號的大小增加到 64 位元 (從 32 位元增加)，同時保留範圍，並將最高順序位元集指定為 Fuchsia 保留用途。
- 將墓誌銘序數更新為
0xFFFFFFFFFFFFFFFF(從0xFFFFFFFF更新)； - 使用交易標頭的旗標欄位，將序數大小增加。
- 並停止使用
[FragileBase]屬性。
與其他 RFC 的關係
此 RFC 已由下列 RFC 取代：
提振精神
從遠端對抗破損
我們花了一段時間研究組合模型引發的斷裂問題。
簡而言之，當 Child 通訊協定組合 Parent 通訊協定時，Parent 可能會在後續引入與 Child 中定義的函式相衝突的函式。這項變更可能在 Parent 中進行，但未察覺在 Child 通訊協定中造成的「遠端」中斷。
以目前的序號雜湊法為例，如果有 1,000 個方法，就會有 10,000 分之 2 的機率發生協定衝突。考量到 FIDL 中需要建構及表達的通訊協定 (和預期的通訊協定) 數量眾多，這很有可能會發生。我們已使用暫時性註解 [FragileBase] 來指出這個問題，並讓開發人員瞭解這個問題。
透過增加方法序數專用的位元數量，我們可以將衝突的機率降低到可接受的程度，以便考慮在實際上不存在的距離中發生破損的問題。
方法序號的大小
一般生日問題可清楚說明衝突的機率。我們有 D = 2^k 種可能性 (「天」)，並且在 N 種方法 (「人」) 中，找出兩種方法發生碰撞的機率 (「相同的生日」)。
如果我們將百萬分之一的門檻視為願意容許的最大衝突機率，那麼方法的最大數量會是：
- 31 位元：約 60
- 39 位元：約 1 千
- 47 位元：約 16k
- 52 位元：約 95k
- 63 位元：約 4.3M
考量上述因素，47 位元以上的選擇是合理的。我們選擇 63 位元還有其他幾個原因：
- 實際上，在 JSON 中使用標準剖析器 (例如 Go 或 Python) 將序數設為數字是安全的。(在 JSON IR 的 2 版中，我們打算將序數包裝為字串)。
- 由於控制訊息有空位，因此如果日後需要分配其他標記，就會有足夠的空間。目前唯一的控制訊息是墓誌銘文。
我們為保留的序號新增高位元，因此序號的產生大小為 64 位元。
我們考慮將位元數限制為 52 位元 (含控制訊息共 53 位元)，因為這是 IEEE754 中可表示的最大正整數，可在僅支援雙精度 (例如 JavaScript)。不過，這些語言仍需要操控序數，才能將序數放入網路，因此需要進一步的機制才能存取組成雙精度的個別位元組。
設計
雜湊計算
RFC-0020：介面序號雜湊中所述的雜湊計算方式稍有變動。它應該會產生 64 位元數字，且計算雜湊的字串為 <library>/<top level declaration>.<member> (依據 RFC-0043：文件註解格式)。
雜湊序號是根據下列項目的 SHA-256 雜湊值衍生而來：
- library name - 以 UTF-8 編碼；沒有尾隨的 \0
- 「/」— 斜線字元，ASCII
0x2f - protocol name：採用 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、保留、標記和目前的序號。預留欄位會用於 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
}
兩個「Get」方法都會具有相同的 M 位元 (這是「Get」的雜湊值)。不過，P 位元會有所不同；一個是 alternative/Parent 的雜湊，另一個則是 alternative/Child 的雜湊。
從可行性角度來看，使用與上述相似的數值方法，我們有：
- 我們預期有幾個通訊協定？100k 的順序是合理的。
- → 需要 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)))