| 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 个左右方法的协议，发生冲突的几率约为 1/5,000。考虑到要使用 FIDL 构建和表达的协议（以及预期协议）数量众多，这种情况很可能会发生。
我们已采用临时注释 [FragileBase] 来指明此问题，并让开发者了解此问题。
通过增加专用于方法序号的位数，我们可以将冲突概率降低到令人满意的水平，从而在实际应用中将此中断问题视为不存在。
方法序号的大小调整
广义生日问题很好地描述了发生碰撞的概率。我们有 D = 2^k 种可能性（“天数”），现在要寻找在 N 种方法（“人”）中，其中两种方法恰好发生冲突（“同一天生日”）的概率。
如果我们认为百万分之一的碰撞概率是我们愿意容忍的最大碰撞概率，那么最终得到的方法数量上限为：
- 31 位：~60
- 39 位：~1k
- 47 位：约 1.6 万
- 52 位：约 9.5 万
- 63 位：约 430 万
鉴于上述情况，47 位或更长的密钥是合理的选择。 我们之所以选择 63 位，还有以下几个原因：
- 实际上，使用标准解析器（例如 Go 或 Python 中的解析器）将序数作为数字包含在 JSON 中是安全的。 （在 JSON IR 的 v2 中，我们计划将序数封装为字符串。）
- 由于控制消息仍有空间，因此如果以后需要分配其他标志，仍有空间可供使用。目前，唯一现有的控制消息是墓志铭。
我们为预留的序号添加了一个高位，因此序号的最终大小为 64 位。
我们曾考虑将限制设为 52 位（含控制消息总共 53 位），因为这是 IEEE754 中可表示的最大正整数，这使得在仅支持双精度浮点数的语言（例如 JavaScript）。 不过，这些语言仍需要处理序数才能将其放置在网络上，因此需要一种进一步的机制来访问构成 double 的各个字节。
设计
哈希值计算
对 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() 使用 - 高位未设置的
txid保留供用户空间使用 - 如需详细了解
txid分配，请参阅 zx_channel_call()
- 设置了高位的
uint32 reserved0，预留供日后使用。uint64 ordinal- 零序数无效。
- 大于
0xfffffffffffff的序号是预留的。
JSON IR
没有变化，并且鉴于开发者定义的序号最多可以选择 52 位，标准 JSON 解析器可以将此值解析为 64 位浮点数，而不会损失精度。
其他序数
我们有表格中的序数和可扩展的联合。 我们不打算更改这些内容：在这两种情况下，目前都不存在远程中断场景（例如，没有可扩展的联合组成其他可扩展的联合）。
实施策略
与从显式序号到哈希序号的策略类似。
工效学设计
没有变化。
文档和示例
需要修改线上传输格式。
向后兼容性
不向后兼容。
性能
预计不会有任何影响。 方法和事件调度现在必须在 64 位整数（而非 32 位整数）上完成，预计这不会有任何区别。
安全
对安全性没有影响。 如需了解性能可通过其他方案得到提升的安全性驱动型使用情形，请参阅替代方案：识别协议和方法。
测试
用于序数计算的单元测试。 遵循与 RFC-0020：接口序号哈希 类似的模式。
替代方案：识别协议和方法
我们设想的沙盒服务可以保护其他服务免遭未经授权的使用，即一种 FIDL 消息防火墙。在构建此类沙盒服务时，高效引用一组消息（“允许的消息”）会很有用。可以想象一下，使用协议定义这组消息。
在这种情况下，拥有两个标识符（一个用于协议，一个用于方法）会很有用（与上述仅提供一个标识符的提议方案相反）。
我们来考虑一下以下替代方案：
- 用于协议名称哈希的 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 位
因此，我们认为这种替代方案不可行。
此外，考虑到沙箱使用情形，由于协议组合（方法可能来自多个源协议），仅针对一个协议标识符进行匹配是不够的。因此，虽然优化后的路径可能受益于单个标识符，但一般情况下需要通过某种数据结构进行查找才能实现高效。
附录：碰撞概率
结果
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)))