RFC-0029：递增方法序数

RFC-0029：递增方法序数
状态已接受
领域
  • FIDL
说明

将方法序数的大小增加到 64 位（从 32 位增加到 64 位），同时保持为 Fuchsia 保留用例设置的最高顺序位的范围。将表层序数更新为 0xFFFFFFFFFFFFFFFF（从 0xFFFFFFFF）。使用事务标头的 flag 字段打包增加的序数大小。并停止使用 FragileBase 属性。
作者
  • pascallouis@google.com
提交日期（年-月-日）2019-02-14
审核日期（年-月-日）2019-02-28

修改此 RFC

修改 RFC 元数据

总结

我们建议：

  1. 为了将方法序数的大小增加到 64 位（从 32 位提高到 64 位），同时保持为 Fuchsia 保留使用情况设置最高阶位的范围；
  2. 将 epitaph 序数更新为 0xFFFFFFFFFFFFFFFF（从 0xFFFFFFFF）；
  3. 使用事务标头的标志字段打包增加的序数大小；
  4. 停止使用 [FragileBase] 属性。

与其他 RFC 的关系

此 RFC 已被取代：

设计初衷

解决远距离损坏问题

我们花了一段时间研究在一定距离处破损的问题，这是合成模型引入的。

简而言之，当 Child 协议构成 Parent 协议时，Parent 可能会在与 Child 中定义的方法冲突后引入一个方法。此更改可能是在 Parent 中进行的，而没有意识到 Child 协议中导致“在一定距离内”导致的破坏。

按照我们目前使用的序数哈希方案，大约有 2/10000 的可能性会产生协议冲突（大约有 1000 种方法）。考虑到需要构建并以 FIDL 表示的大量协议（和预期的协议），很可能是这样做的。我们已采用临时注解 [FragileBase] 来指明此问题，并告知开发者此问题。

通过增加方法序数的专用位数，我们可以将碰撞概率降低到令人满意的程度，从而考虑在不存在距离导致的破坏问题（在实践中）。

方法序数的大小

广义生日问题很好地描述了发生冲突的概率。我们有 D = 2^k 种可能性（“天”），并寻找在 N 个方法（“people”）中，其中两种方法发生碰撞（“同一生日”）的可能性。

如果我们将 100 万个概率的阈值视为我们愿意容忍的最大碰撞概率，则最终的方法数量上限为：

  • 31 位：约 60
  • 39 位：约 1k
  • 47 位：约 16k
  • 52 位：约 95k
  • 63 位：约 430 万

根据上述情况，47 位或以上是合理的选择。 我们选择 63 位的原因如下：

  • 在实践中，使用标准解析器（例如，在 Go 或 Python 中）将序数设置为 JSON 中的数字是安全的。（在 v2 的 JSON IR 中，我们计划将序数封装为字符串。）
  • 由于还有空间来存储控制消息，因此如果稍后需要分配这些标志，也会有空间来存储这些标志。现如今，唯一现有的控制讯息是 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、预留、标志和当前序数。预留字段供 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 消息设置一种防火墙。在构建此类沙盒服务时，高效引用一组消息（“允许的消息”）会很有用。可以想象一下，使用协议定义这组消息。

在这种情况下，使用两个标识符（一个用于协议，一个用于方法）会很有用（与上述方案（仅提供一个标识符）不同。

我们来考虑一下这种替代方案，其中：

  • 协议名称哈希的 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 位
  • 我们期望使用多少种方法？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)))