RFC-0020：接口序数哈希

“60% 的时间，它都是面试问题的答案”

摘要

我们建议移除程序员手动指定接口方法序号的功能 ¹。相反，编译器会根据完全限定的方法名称（即库名称、接口名称和方法名称）的哈希值生成序号。方法重命名将通过新的 Selector 属性实现 ABI 兼容性（请参阅下文）。

我们专门限制此 FTP 仅用于为接口提出序号哈希建议；不适用于枚举、表或可扩展的联合。我们认为这些结构的使用情形差异很大，需要进一步调查并采用不同的 FTP。

示例

目前，FIDL 作者会编写以下代码：

library foo;

interface Science {
    1: Hypothesize();
    2: Investigate();
    3: Explode();
    4: Reproduce();
};

此 FTP 将允许舍弃序数索引：

interface Science {
    Hypothesize();  // look, no ordinals!
    Investigate();
    Explode();
    Reproduce();
};

在底层，编译器实际上会生成如下所示的序号：

interface Science {
    // ordinal = SHA-256 of the fully-qualified method name,
    // i.e. "foo.Science/MethodName", truncated to 32 bits
    0xf0b6ede8: Hypothesize();
    0x1c50e6df: Investigate();
    0xff408f25: Explode();
    0x0c2a400e: Reproduce();
};

设计初衷

• 手动指定序号在很大程度上是机械性的。 如果您无需考虑这些问题，编写接口的工作量就会减少。
• 如果使用良好的哈希，则极不可能出现哈希导致序号冲突的情况，这比人工手动编写序号要好得多（尤其是在使用接口继承的情况下）。如需了解详情，请参阅下文的序号冲突部分。
• 程序员目前必须确保不同方法的序号不会冲突。对于方法较少的接口，这很容易，但如果接口有很多方法，这可能会变得不简单。序数编号有不同的编码风格和思想流派，这会导致编码风格不一致。
  • 大多数接口从 1 开始，然后向上递增。
  • 不过，有些作者更喜欢按范围对不同的接口方法进行分组（例如，1-10、100-110 等）。
  • 移除手动编号的序数词也可消除这种不一致的样式，并让作者无需再决定使用哪种样式。
• 接口继承可能会导致序号意外冲突。目前已尝试两次解决此问题：
  • FTP-010（已拒绝）提议添加 OrdinalRange 属性，以便接口继承更具可预测性；但该提议遭到了拒绝。
  • FragileBase ² 是当前的临时解决方案，但无法解决确保序数不冲突的核心问题。
  • 如果对序号进行哈希处理，并使用接口和库名称来计算哈希值，那么对序号进行哈希处理不会导致序号冲突，从而解决接口继承问题（极少数的哈希冲突除外）。

设计

哈希

哈希处理后的序号是通过对以下内容进行 SHA-256 哈希处理得出的：

library name (encoded as UTF-8; no trailing \0)
".", ASCII 0x2e
interface name (encoded as UTF-8; no trailing \0)
"/", ASCII 0x2f
method name (encoded as UTF-8; no trailing \0)

例如，以下 FIDL 声明：

library foo;

interface Science {
    Hypothesize();
    Investigate();
    Explode();
    Reproduce();
};

将具有以下用于计算序号哈希的字节模式：

foo.Science/Hypothesize
foo.Science/Investigate
foo.Science/Explode
foo.Science/Reproduce

由于 fidlc 已经以这种格式输出完全限定的方法名称（请参阅 fidlc 的 NameName() 方法），因此使用了 . 和 / 分隔符。

计算出 SHA-256 哈希后：

1. 提取 SHA-256 哈希值的高 32 位（例如， echo -n foo.Science.Hypothesize | shasum -a 256 | head -c8)
2. 将高位设置为 0，从而生成一个有效的 31 位哈希值，该值会零填充到 32 位。（由于 FIDL 传输格式保留了 32 位序号中的最高有效位，因此使用了 31 位。）

在伪代码中：

full_hash = sha256(library_name + "." + interface_name + "/" + method_name)
ordinal = full_hash[0] |
        full_hash[1] << 8 |
        full_hash[2] << 16 |
        full_hash[3] << 24;
ordinal &= 0x7fffffff;

选择器属性和方法重命名

我们定义了一个 Selector 属性，编译器将使用该属性来计算哈希序号，而不是使用方法名称。如果方法名称没有 Selector 属性，则该方法名称将用作 Selector。（界面和库名称仍用于哈希计算。）

Selector 可用于重命名方法，而不会破坏 ABI 兼容性，这是手动指定的序号的一项优势。例如，如果我们希望将 Science 接口中的 Investigate 方法重命名为 Experiment，可以编写：

interface Science {
    [Selector="Investigate"] Experiment();
};

我们仅允许在方法上使用 Selector 属性。重命名库的情况很少见，在这种情况下，保持 ABI 兼容性并不是首要任务。重命名接口也是如此。此外，重命名的接口与 Discoverable 属性的互动会令人困惑：哪个名称是可发现的名称？

序数冲突与冲突解决

如果哈希序号与同一接口中的另一个哈希序号发生冲突，编译器将发出错误，并依靠人工指定 Selector 属性来解决冲突 ³。

例如，如果方法名称 Hypothesize 与方法名称 Investigate 冲突，我们可以向 Hypothesize 添加 Selector 以避免冲突：

interface Science {
    [Selector="Hypothesize_"] Hypothesize();
    Investigate();  // should no longer conflict with Hypothesize_
};

我们将更新 FIDL API 评分标准，建议为 Selector 的方法名称附加“_”以解决冲突。fidlc也会建议此修复。

请注意，序号只需在每个接口中保持唯一，与手动指定的序号类似。如果我们希望序号在所有接口中都是唯一的，则应在另一个 FTP 中提出此建议。

粗略计算表明，如果接口上有 100 种方法，那么使用 31 位时发生冲突的几率为 0.0003%，因此我们预计哈希冲突非常罕见。

选择器 Bikeshed

以下是针对 Selector 的其他建议：

• WireName（abarth）
• OriginalName（ctiller）
• Salt（abarth；略有不同，因为它建议添加编译器指定的 salt，而不是备用名称）
• OrdinalName

我们选择了 Selector，因为我们认为它比 WireName 或 OriginalName 更能反映属性的意图。

我们之所以选择让程序员指定序号名称，而不是序号索引，有以下几个原因：

• 要求提供索引会更加繁琐（例如，在发生冲突时复制并粘贴原始 SHA-256 哈希值），
• 指定序号名称可实现 ABI 兼容的方法重命名，
• 指定名称而不是索引，可以说是在程序员编写接口时，让其脑海中的抽象级别保持不变，而不是降低一个抽象级别，要求他们考虑序号。

零序数

零是无效的序数。如果方法名称的哈希值为零，编译器会将其视为哈希冲突，并要求用户指定一个哈希值不为零的 Selector。

我们曾考虑让 fidlc 通过确定性转换自动重新哈希名称，但认为：

• 任何此类算法都将是非显而易见的，并且
• 零值情况极为罕见，

因此，这种方法不值得在人体工程学和编译器实现方面都进行复杂化处理。

事件

此 FTP 还涵盖了事件，根据 FIDL 语言文档 ⁴，事件被视为方法的一个子集。

编译器和绑定变更

我们认为，只需修改 fidlc 即可支持序数哈希；代码生成后端无需修改。这是因为 fidlc 会计算序数，并将其以 JSON IR 形式发送到后端。

绑定无需更改。

实施策略

我们打算分阶段实现此功能：

1. 向 fidlc 添加了用于计算哈希值的代码。
2. 为库添加了属性支持。
3. 向 Fuchsia 工程团队广播了更改意图，以便他们了解潜在问题。 a. 建议在某个日期弃用手动序号，届时我们预计下一步已完成。
4. 在同一 CL 中： a. 修改 FIDL 语法的 interface-method 规则，使序号成为可选；有关详情，请参阅下文。 b. 忽略手动指定的序号，并使用传递给代码生成后端之序号名称的哈希序号。 c. 通过添加 Selector 属性手动修复所有现有的哈希冲突。
5. 测试更改两周，确保没有生产问题。 a. 在此时间段内编写的新 FIDL 接口不应使用序号。 b. 人工序号被视为已弃用，但 fidlc 不会针对此情况发出警告。 c. 与团队合作，确保界面中没有手动指定的序号。 d. 在两周结束时，更新 FIDL 格式化程序以移除序数，并将其大规模应用于整个 Fuchsia 树。
6. 移除对手动指定序数的支持。

上述是软过渡；将 fidlc 更改为使用哈希序号（步骤 4b）不应破坏滚动器，因为滚动器是从整个树的单个版本构建的。

在 jeremymanson@google.com 对此 FTP 的实现中，他选择优先使用手动指定的序号，而不是哈希序号，这与上述步骤 4b 不同。这样一来，所有使用手动指定的序号的现有接口都将保持 ABI 兼容，并且仅在未指定序号时使用哈希序号。

工效学设计

优点：

• 写作界面应该更简单。

缺点：

• 程序员需要了解一个新属性 Selector，该属性有两个用途：重命名和冲突解决。
• 更改方法名称会破坏 ABI 兼容性，这一点可能并不明显，而程序员指定的序号则不会出现这种情况。 用户教育（例如更好的文档）可以缓解这种情况。
  • 请注意，其他组件系统（例如 COM 和 Objective-C）通常也会在接口方法重命名时破坏 ABI 兼容性。因此，使用过类似系统的开发者可能对这种行为很熟悉。
• 失去对序号的手动控制可能会导致在异常情况下（例如在同一 Zircon 通道上使用多个 FIDL 接口）调试能力下降。

请注意，作者最初提出此 FTP 主要是出于人体工效学方面的考虑。

文档和示例

我们预计会更改 FIDL 属性、语法、语言和线格式文档。还应更新 API 可读性评分标准文档，如Selector 部分中所述。

向后兼容性

• 根据设计，哈希序号与手动指定的序号在 ABI 方面不兼容。我们预计这不会成为问题，因为
  • fidlc 更改是二元的（系统将使用哈希异或或手动序数），并且
  • fidlc 用于构建整个树，因此
  • 树的所有部分都将始终使用所选的序数方案。
• 哈希序号是 API（源）兼容的。现有源文件将保持兼容；手动序号将被弃用（请参阅“实现策略”）。
• 如果使用两个不同的 fidlc build（即平台源代码树的两个不同 build），并且使用 FIDL 接口跨机器进行通信，则会发生错误。作者目前未发现任何使用此功能的场景，因此这应该不是问题。

性能

我们预计 fidlc 的减速可以忽略不计，因为它现在必须对接口中的所有方法名称进行哈希处理才能计算它们。

我们预计运行时性能影响微乎其微。 编译器可能已为之前较小且连续的手动指定序号生成了跳转表，在使用哈希序号时，这些跳转表将变为通过稀疏序号空间进行的二分搜索。同一机制也可能会以微不足道的方式影响二进制文件大小。（表驱动调度可能会缓解大小和速度方面的问题。）

安全

我们预计不会出现运行时安全问题，因为序号哈希除了更改通过网络发送的序号值之外，没有其他运行时更改。

使用加密哈希 (SHA-256) 可能会让一些人认为哈希需要具有加密强度；我们认为不存在安全问题，因为：

• FIDL 编译器会在编译时检查是否存在哈希冲突，并要求人工输入来解决这些冲突；
• 我们使用 SHA-256 不是出于加密目的，而是因为我们希望获得极不可能导致冲突的哈希值。CRC-32（甚至 strlen()）也可以，但可能会导致更多冲突，这只会带来不便。

截断 SHA-256 哈希值可能也会让一些人担心，但我们同样认为不存在安全问题，因为 FIDL 编译器会静态检查哈希冲突 ⁵。

测试

ianloic@google.com 已分析现有的 FIDL 接口，并确定不存在哈希冲突。

我们将仔细考虑如何测试实际的哈希冲突情况，因为人为生成具有良好哈希的哈希冲突非常困难（这是设计使然）。

否则，只需进行典型的单元测试、CQ 测试、兼容性测试和手动测试，即可确保序数哈希处理的稳健性。

缺点、替代方案和未知因素

此 FTP 仅有意针对接口的序号哈希处理。 它不会建议更改枚举、表或可扩展联合的已手动枚举的序号。

jeffbrown@google.com 建议使用完美哈希，并已考虑该建议。 FTP 作者不太熟悉完美哈希方案，但认为随着时间的推移，添加额外的方法会更改现有方法的哈希，从而破坏 ABI 兼容性，使完美哈希不适用。动态完美哈希可能可行，但会引发有关更改哈希的相同问题，并且与标准哈希相比，动态完美哈希的知名度较低，也更复杂，因此不值得进一步研究。

移除手动序号的另一种方法是通过网络发送完整的方法名称，许多（大多数？）其他 RPC 系统都采用这种方法（请参阅下方的参考资料）。这会带来运行时性能方面的影响，可以说与 FIDL 的预期使用情形相冲突。

我们考虑了能够指定所用哈希，以便在 SHA-256 出现其他哈希可以解决的问题时，能够更改哈希。 这种设计在安全应用中很常见，因为广泛使用的加密哈希日后可能会发现漏洞。不过，指定哈希可能需要更改有线格式，并要求所有语言绑定实现代码来选择哈希算法，这会大大增加编译器和绑定代码的复杂性。 我们认为这种权衡并不值得。 我们知道，git 也曾对 SHA-1 持这种态度，现在在一定程度上改变了这一决定，但我们认为我们的使用情形与 git 的使用情形有很大不同，足以证明将哈希算法硬编码是合理的。

探索

• 一种节省空间的识别方法的方式可能会导致方法的高效第一类表示，从而使方法成为第一类。
  • 例如，这可以使方法在 FIDL 调用中用作实参，或者使 FIDL 方法返回另一个方法作为结果。可以说，目前已经存在一些使用情形，其中方法会返回一个具有单个方法的接口，作为返回实际方法的代理。
• 建议的 31 位哈希可以扩展为，例如，64/128/53 位；SHA-256 提供大量位。
• 将 ordinal 重命名为 selector，这是一个现有概念，在其他语言和组件系统中具有相同用途。
• 区分方法名称和接口名称可能很有价值，这样我们就可以获得两个不同的数据块。 这样一来，您就可以唯一地引用接口名称和方法名称。 我们可能需要超过 32 位。
• 如上所述，枚举、表格和可扩展的联合不在范围内。 不过，我们认为此 FTP 仍可能适用于他们。 初步想法：
  • 我们不确定枚举是否需要此功能。 简单且标准化的连续整数编号似乎就足够了。
  • 这可能可以直接应用于可扩展的联合。
  • 表需要采用不同的序列化格式才能采用序数哈希，因为序数目前需要连续，才能实现紧凑的表示形式。
• FIDL 目前保留了序号高位，并在文档中明确指出，一系列高位旨在用作控制流等。作者认为，这方面的原因之一可能还与序号冲突有关。我们是否要重新审视这个问题？
  • 将序号空间扩展到 64 位（如上所述）将在很大程度上解决此问题。
  • abarth@google.com 在 Fuchsia IPC 聊天室中建议仅预留 0xFFFFxxxx。
• 我们可以将方法的实参类型纳入计算出的哈希值中，这样一来，如果我们将来需要，就可以支持方法重载。
  • jeffbrown@google.com 提到，对完整的方法签名进行哈希处理可能会限制接口扩展的机会，并且重载在许多编程语言中映射效果不佳。
• 由于在使用接口继承时，序号哈希应能解决序号冲突问题，因此也可以移除 FragileBase 属性。
  • 代码搜索显示 FragileBase 的使用次数约为 9 次。
• 作者担心，如果许多方法都带有 Selector 属性，那么随着时间的推移，接口可能会变得难以阅读。
  • 解决此问题的一种方法是采用类似于 Objective-C 类别或 C# 部分类的方法，其中已声明的现有接口可以“扩展”，以便在单独的声明中向其添加属性。

在先技术和参考资料

有趣的是，我们不知道有任何其他方法调度或 RPC 系统使用方法名称的哈希来标识要调用的方法。

大多数 RPC 系统都按名称调用方法（例如 gRPC/Protobuf 服务、Thrift、D-Bus）。对于进程内方法调用，Objective-C 使用保证唯一的 char* 指针值（称为选择器）来标识应在类上调用的方法。Objective-C 运行时可以将选择器映射到字符串化的方法名称，反之亦然。对于进程外方法调用，Objective-C 分布式对象使用方法名称进行调用。COM 直接使用 C++ vtable 进行进程内调用，因此依赖于 ABI 和编译器支持来实现方法调度。apang@google.com 在 ctiller@google.com 的 Phickle 提案中建议对表进行序号哈希处理。ianloic@google.com 和 apang@google.com 于 2018 年 10 月 18 日（周四）会面，讨论了此问题。