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 中提出。

粗略计算表明，如果接口中有 31 位和 100 个方法，则冲突的几率为 0.0003%，因此我们预计哈希冲突非常罕见。

选择器 Bikeshed

针对 Selector 还有其他建议：

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

我们之所以选择 Selector，是因为我们认为它比 WireName 或 OriginalName 更能准确反映该属性的意图。

我们之所以选择让程序员指定序数名称（而非序数索引），有以下几点原因：

• 需要索引会更麻烦（例如，在发生冲突时复制并粘贴原始 SHA-256 哈希值），
• 指定序数名称可启用 ABI 兼容的方法重命名，并且
• 指定名称而非编号可以让程序员在编写接口时在脑海中保持相同的抽象级别，而不是降低一级抽象级别，从而需要他们考虑序数。

零序数

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

我们曾考虑让 fidlc 通过确定性转换自动重新对名称进行哈希处理，但认为这样做存在以下问题：

• 任何此类算法都不会显而易见，并且
• 零个案例极其罕见，

因此，这种方法不值得让工效学和编译器实现变得复杂。

事件

本 FTP 还介绍了事件，FIDL 语言文档 ⁴ 将事件视为方法的子集。

编译器和绑定变更

我们认为，只有 fidlc 需要修改才能支持序数哈希；代码生成后端无需修改。这是因为 fidlc 会计算序数，并将其在 JSON IR 中发送到后端。

无需更改绑定。

实施策略

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

1. 向 fidlc 添加代码以计算哈希值。
2. 向库添加了对属性的支持。
3. 向 fuchsia eng 广播 intent-to-change，以便他们了解潜在问题。 a. 建议在我们预计完成后续步骤的某个日期弃用手动序数。
4. 在同一 CL 中： a. 修改 FIDL 语法的接口方法规则，使序数成为可选项；如需了解详情，请参阅下文。 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 属性、语法、语言和线格格式文档。如 Selector 部分所述，还应更新 API 可读性评分标准文档。

向后兼容性

• 出于设计目的，经过哈希处理的序数与手动指定的序数在 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 采取了这种态度，并且现在在某种程度上对此决定进行了回溯，但我们认为我们的用例有足够的不同之处，足以证明对哈希算法进行硬编码是合理的。

探索

• 一种节省空间的方法来标识方法可以导致方法的高效第一类表示法，从而使方法成为第一类。
  • 例如，这可以让方法在 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 日星期四会面，在白板上讨论了这个问题。