| RFC-0029：增加方法序数 | |
|---|---|
| 状态 | 已接受 |
| 区域 |
|
| 说明 | 将方法序数的大小从 32 位增加到 64 位，同时将最高阶位设置为 Fuchsia 预留用途，以保持范围不变。将墓志铭序数更新为 0xFFFFFFFFFFFFFFFF（从 0xFFFFFFFF）。使用事务标头的 flags 字段打包增大的序数大小。并停止使用 FragileBase 属性。 |
| 作者 | |
| 提交日期（年-月-日） | 2019-02-14 |
| 审核日期（年-月-日） | 2019-02-28 |
摘要
我们建议：
- 将方法序数的大小增加到 64 位（从 32 位增加），同时将最高序数位设置为 Fuchsia 预留用途，以保持范围不变；
- 将墓志铭序数更新为
0xFFFFFFFFFFFFFFFF（从0xFFFFFFFF更新）； - 使用事务标头的 flags 字段打包增大的序数大小；
- 并停止使用
[FragileBase]属性。
与其他 RFC 的关系
此 RFC 已被以下 RFC 取代：
设计初衷
远程防范断裂
我们花了一些时间研究组合模型引入的远程断裂问题。
简而言之，当 Child 协议组合 Parent 协议时，Parent 可能会在之后引入与 Child 中定义的方法冲突的方法。这项更改可能在 Parent 中进行，而没有意识到 Child 协议中“远程”造成的破坏。
使用我们目前的序数哈希方案，对于有 1,000 种方法的协议，发生碰撞的概率大约为 1 万分之 2。鉴于 FIDL 中需要构建和表达的大量协议（以及预期协议），这种情况很可能发生。我们使用了临时注解 [FragileBase] 来指明此问题，以便开发者知晓此问题。
通过增加专用于方法序数的位数，我们可以将碰撞概率降低到一个令人满意的水平，从而认为远程断开连接问题不存在（在实际操作中）。
方法序数的大小
一般化生日问题很好地描述了冲突的概率。我们有 D = 2^k 种可能性（“天”），并且要找出在 N 种方法（“人”）中，有两种方法恰好重合（“生日相同”）的几率。
如果我们将 1 / 100 万的几率作为我们愿意容忍的最大碰撞概率，最终得到的方法数量上限为：
- 31 位：约 60
- 39 位：约 1k
- 47 位：约 16k
- 52 位：约 95,000
- 63 位：约 430 万
鉴于上述情况，47 位或更高位数是合理的选择。 我们选择 63 位还有一些其他原因：
- 在实践中，使用标准解析器（例如 Go 或 Python）将序数作为数字在 JSON 中表示是安全的。（在 JSON IR 的 v2 中，我们计划将序数封装为字符串。）
- 由于保留了控制消息的空间，因此如果日后需要分配其他标志，也还有空间。目前，唯一存在的控制消息是 epitaph。
我们为预留的序数添加了一个高位，因此序数的最终大小为 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、预留、标志和当前序数。预留字段由墓志铭的错误代码使用。因此，我们建议使用 flags 字段（目前未使用）将序数字段从 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)))