| RFC-0029：增加方法序數 | |
|---|---|
| 狀態 | 已接受 |
| 區域 |
|
| 說明 | 將方法序數的大小增加至 64 位元 (從 32 位元起)，同時維持最高位元集範圍，以供 Fuchsia 保留使用。將墓誌銘序數更新為 0xFFFFFFFFFFFFFFFF (從 0xFFFFFFFF 開始)。使用交易標頭的旗標欄位，封裝增加的序數大小。並停止使用 FragileBase 屬性。 |
| 作者 | |
| 提交日期 (年-月-日) | 2019-02-14 |
| 審查日期 (年-月-日) | 2019-02-28 |
摘要
我們建議：
- 將方法序數的大小增加至 64 位元 (從 32 位元起)，同時維持最高位元集範圍，以供 Fuchsia 保留使用；
- 將墓誌銘序數更新為
0xFFFFFFFFFFFFFFFF(從0xFFFFFFFF開始)； - 使用交易標頭的旗標欄位，封裝增加的序數大小；
- 並停止使用
[FragileBase]屬性。
與其他 RFC 的關係
這項 RFC 已由下列項目取代：
提振精神
遠端解決中斷問題
我們已研究一段時間，發現組合模型會導致遠距離的物件斷裂。
簡而言之，當 Child 通訊協定組成 Parent 通訊協定時，Parent 可能會事後導入與 Child 中定義的方法衝突的方法。這項變更可能是在 Parent 中進行，但並未意識到「遠端」Child 通訊協定中發生的中斷。
以目前的序數雜湊配置而言，如果通訊協定有 1,000 個方法，發生衝突的機率約為 2/10,000。鑑於要建構及以 FIDL 表示的通訊協定數量龐大 (且預計會更多)，這種情況很可能發生。我們已暫時使用 [FragileBase] 註解來標示這個問題，並通知開發人員。
增加專用於方法序數的位元數，可將碰撞機率降至令人滿意的程度，因此實際上可視為不存在這個中斷問題。
方法序數大小
廣義生日問題可充分說明發生碰撞的機率。我們有 D = 2^k 種可能性 (「天數」)，並想找出在 N 種方法 (「人數」) 中，有兩種方法發生衝突 (「生日相同」) 的機率。
如果我們將容許的最大碰撞機率設為百萬分之一，則方法數量上限為：
- 31 位元：~60
- 39 位元：約 1,000 個
- 47 位元：約 16,000 個字元
- 52 位元：約 95,000
- 63 位元：約 430 萬
因此，47 位元以上是合理的選擇。 我們選擇 63 位元的原因如下：
- 在實務上，使用標準剖析器 (例如 Go 或 Python) 時，序數以 JSON 格式的數字表示是安全的。(在 JSON IR 的第 2 版中，我們計畫將序數包裝為字串)。
- 控制訊息仍有空間，因此日後如有需要，可分配其他標記。目前唯一現有的控制訊息是墓誌銘。
我們為保留的序數新增高位元，因此序數的結果大小為 64 位元。
我們考慮將位元限制為 52 位元 (含控制訊息則為 53 位元)，因為這是 IEEE754 中可表示的最大正整數，因此在僅支援雙精度浮點數的語言 (例如 JavaScript)。 不過，這些語言仍需處理序數，才能將序數放在連線上，因此需要其他機制來存取組成倍數的個別位元組。
設計
雜湊值計算
RFC-0020：介面序數雜湊中導入的雜湊計算方式略有變更。這應該會產生 64 位元數字，且計算雜湊的字串為 <library>/<top level declaration>.<member> (根據 RFC-0043：文件註解格式)。
雜湊序數是透過下列項目的 SHA-256 雜湊衍生而來：
- 程式庫名稱 - 編碼為 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、保留、旗標和目前序數。預留欄位用於墓誌銘的錯誤代碼。 因此，我們建議使用旗標欄位 (目前未使用)，將序數欄位從 4 個位元組增加到 8 個位元組。
標頭的新定義如下：
zx_txid_t txid、交易 ID (32 位元)txid，且高位元集保留供 zx_channel_call() 使用txids with the high bit unset are reserved for use by userspace- 如要進一步瞭解
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 位元
- 我們預期會有多少種方法？1,000 個左右的順序是合理的。
- → 需要 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)))