| RFC-0029：增加方法序数 | |
|---|---|
| 状态 | 已接受 |
| 领域 |
|
| 说明 | 将方法序数的大小增加到 64 位（从 32 位增加到 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 协议。
使用我们今天的序号哈希架构，大约有 2/10,000
约 1,000 种方法发生冲突。
考虑到大量的协议（和预期
采用 FIDL 进行构建和表达。
我们使用临时注解 [FragileBase] 来指明这一点
并提醒开发者注意这个问题
通过增加专用于方法序数的位数， 碰撞概率达到令人满意的水平，以便考虑此问题 但实际上远远不存在的破损情况
方法序数的大小
广义生日问题很好地描述了
冲突。
我们有 D = 2^k 种可能性（“天”），正在寻找机会
在 N 个方法（“人类”）中，其中两种方法碰巧
（“同一生日”）。
如果我们将一百万次 1 次机会的阈值视为 冲突概率，最终得出一个 包括：
- 31 位：~60
- 39 位：约 1k
- 47 位：约 16k
- 52 位：约 95k
- 63 位：~4.3M
根据上述情况，选择 47 位或以上是合理的选择。 我们选择 63 位的原因如下：
- 在实践中，使用标准的 JSON 格式，将序号作为数字存储是安全的 （例如 Go 或 Python）。 （在 v2 的 JSON IR 中，我们计划将序数封装为字符串。）
- 剩余空间用于控制消息，也可用于放置其他标记 应该稍后分配 如今，唯一现有的控制讯息是墓碑。
我们为预留序数添加了一个高位，因此生成的序数大小 为 64 位。
我们考虑过限制为 52 位（控制消息的总和为 53 位） 因为它是 IEEE754 中可表示的最大正整数， 因此在仅支持 双精度数（例如JavaScript）。 然而，这些语言仍然需要操纵序数，才能将 因此需要进一步的机制来访问 各个字节组成双精度型数据。
设计
哈希计算
“RFC-0020：接口序数”中引入的哈希计算
哈希处理略有改变。
它应该都会生成一个 64 位的数字，以及用来进行哈希处理的字符串
计算公式为：<library>/<top level declaration>.<member>（每
RFC-0043: Documentation Comment Format)。
经过哈希处理的序数通过下列内容的 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 位） <ph type="x-smartling-placeholder">- </ph>
- 具有高位设置的
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。
从可行性的角度来看，使用类似的数值方法 我们可以得到：
- 我们预计有多少个协议？100K 数量是合理的。
- → 需要 P = 52 位
- 我们期望使用多少种方法？1k 的顺序是合理的。
- → 需要 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)))