编码与 Map/Array 容器

序列化方向与解析相反，而且做了一件反直觉的事：从缓冲区尾部往前写。本章拆解反向写入编码器、长度前缀如何”前置”、upb_Array 的倍增增长、upb_Map 与底层开放寻址哈希表，以及确定性输出的排序器。

⚠️ 本章对应的是较新版本的 upb，与一些旧资料有两处差异：① 编码器不再把 ptr/end/buf/limit 直接放进 upb_encstate，而是委托给独立的 upb_BackAlloc 抽象；② 整数键 map 的”数组部分（array part）”优化在此版本已不存在，upb_inttable 现在只是开放寻址哈希表的薄封装。

1. 反向写入编码器

为什么倒着写

wire/encode.c:8 与 wire/internal/encoder.c:8 的开头一句话点题：“We encode backwards, to avoid pre-computing lengths (one-pass encode).”

protobuf 的长度分隔 wire 格式（子消息、字符串、bytes、packed）要求在 payload 前面放一个 varint 字节长度。朴素的正向编码器要么扫两遍（先算所有嵌套长度、再写），要么写占位符再回填（难，因为 varint 长度的宽度取决于值）。upb 两者都绕过：先写 payload、从缓冲尾部往低地址写，等确切字节数已知后再往左”前置”一个长度 varint。因为游标只朝低地址移动，前置只是”往左多写几个字节”。于是序列化严格一遍完成。

由此一个可见后果：消息内字段按逆字段序发射，整块倒着建完后，最终的正向读取顺序才正确。见 encode_message 从最后一个字段往第一个遍历（encoder.c:796-804）。

缓冲抽象 upb_BackAlloc

upb_encstate（encoder.h:34-41）持有 upb_BackAlloc alloc、options、depth、status、_upb_mapsorter sorter、jmp_buf* err。ptr 游标不在结构里——它作为返回值穿过每个 encode_* 函数，从而留在寄存器。

upb_BackAlloc（back_alloc.h:24-28）就是那对”ptr/end”布局，外加一个标志：buf（当前块低端）、limit（高端，写入从这里开始）、standalone（是否独立分配）。已写字节占 [ptr, limit)。Init 把 buf/limit 都指向 1 字节全局哨兵（back_alloc.h:39-40、back_alloc.c:20）——因为 C 禁止 NULL - NULL 指针运算。

关键内联辅助：HasBytes(a, ptr, need) = (ptr - buf) >= need（back_alloc.h:63-67）；Size(a, ptr) = limit - ptr（back_alloc.h:76-78）——编码器据此测量子消息/packed/map 大小（见 §2）。

reserve / 增长

encode_reserve（encoder.c:96-102）：有空间就 ptr - bytes（游标左移）；否则走 out-of-line 的 encode_growbuffer（:85-92），OOM 经 encode_err longjmp（:79-83）。增长（upb_BackAlloc_Grow，back_alloc.c:94-109）：首次从 arena “偷”空间（_upb_Arena_Steal），小消息从不触发独立 malloc；否则 realloc 到更大块，把已写后缀 memcpy 到新块的右端以保住”payload 贴着 limit”的不变量（back_alloc.c:54-92）。块大小指数增长（back_alloc.c:22-52）。

varint 快路径与标量

encode_varint（encoder.c:271-280）：val < 128 且有 1 字节余量则内联写单字节（--ptr; *ptr = val）。更大的值走 encode_longvarint，它有通用版（encoder.c:245-258）和一套 ARM64 手写汇编（用 clz 算 varint 宽度再跳转表，encoder.c:155-240）。encode_scalar（encoder.c:369-455）用一个 CASE 宏一次 reserve tag(5)+value(10) 字节，再用 _unchecked 变体写值和 tag（不重复检查余量）。定长类型经 upb_BigEndian{32,64} 字节交换。

深度限制与顶层流

e->depth 从选项的最大深度初始化（encoder.c:848），每层子消息/组 if (--e->depth == 0) encode_err(...)（:426、:441、:539、:556）。_upb_Encode（:839-853）初始化后，upb_Encoder_Encode（:811-837）setjmp、调 encode_message、按需前置整体长度、用 upb_BackAlloc_Finish 收尾。

2. 长度前缀：先写 payload，再前置 varint

倒写技巧的核心。encode_scalar 的 Message 分支（encoder.c:434-450）：

  1. ptr = encode_message(ptr, e, submsg, subm, &size)（:442）倒着写完整个子消息 payload，size 经 limit - ptr 差值返回。
  2. encode_length_unchecked(ptr, e, size)（:447）前置长度 varint。
  3. encode_tag_unchecked(...)（:448）前置字段 tag。

encode_message 自己测量输出（pre_len = Size(...) 在 :763，*size = Size(...) - pre_len 在 :807）。因为 payload 已经写下，size 精确——无第二遍、无回填。同样模式用于组（先发 EndGroup tag、无长度前缀，:419-433）、map 项（:579-592）、packed 数组（§3）。encode_length（:282-299）会对超 2GB 报 MaxSizeExceeded。

3. upb_Array 与 packed 字段

结构与 tagged 指针 

struct upb_Array {
  uintptr_t data;   // tagged 指针
  size_t    size;   // 元素个数
  size_t    capacity;
};

（message/internal/array.h:30-42）

tagged data 低位打包三样（掩码 array.h:19-21）：bit 0-1 是元素大小 log2（编码：存位 0→lg2 1、1→lg2 4、2→lg2 8、3→lg2 16；编码 bits = lg2 - (lg2!=0)、解码 lg2 = bits + (bits!=0)，array.h:52-65）——让索引用移位 i << lg2 代替乘法；bit 2 是 frozen 标志；upb_Array_DataPtr 把三者掩掉（array.h:67-70）。元素数据内联紧跟结构之后首次分配（array.h:76-93），默认起始容量 4（array.c:24-27）。

倍增增长

_upb_Array_Realloc（array.c:160-185）：new_capacity = max(capacity, 4)，循环 <<= 1 翻倍到 >= min_capacity（:168-173），溢出由 upb_ShlOverflow 守卫，于是 append 摊销 O(1)。还有原地快扩 _upb_Array_TryFastRealloc（array.h:112-121）用 upb_Arena_TryExtend。索引到处用 <<lg2（array.c:29-36）。

packed vs 非 packed 编码

encode_array（encoder.c:457-577）：packed = IsPacked(f)（:460）。无论哪种都后往前遍历数组（与倒写一致）。

  • packed varint：只发值、无每元素 tag；循环后前置整段的一个长度 + 一个 tag（:571-575）。
  • 定长 packed（encode_fixedarray，encoder.c:336-367）：最大的赢点——小端主机、无每元素 tag 时，对整个数组做一次 memcpy（:364-365），因为内存布局已与 wire 布局一致；否则逐元素字节交换。

4. upb_Map 与哈希表

upb_Map 

struct upb_Map {
  char key_size;          // 0 (UPB_MAPTYPE_STRING) 表示字符串
  char val_size;
  bool is_frozen;
  bool is_strtable;       // 选哪个 union 成员
  union { upb_strtable strtable; upb_inttable inttable; } t;
};

（message/internal/map.h:38-47）

_upb_Map_New（map.c:179-195）在构造时选表：键 <= sizeof(uintptr_t) 且非字符串用 inttable，否则 strtable（:183-188）。字符串值堆拷进 arena 按指针存，定长值直接 memcpy 进 8 字节 upb_value（map.h:91-102）。

开放寻址哈希表

entry upb_tabent（hash/common.h:125-136）：{ upb_value val; upb_key key; uintptr_t next; }。next 编码存在性：0 = 空槽、1（kUpb_NoNextTabent）= 链尾、其他 = 指向链中下一项（common.h:151-159）——用 0/1 当哨兵成立，因为真实 upb_tabent* 不可能是地址 0 或 1（静态断言对齐 > 1）。基表 upb_table（common.h:138-145）= { entries; count; mask; }；表大小恒为 2 的幂 = mask+1，桶 = hash & mask（common.c:98-100）。

冲突策略是链式散布 + Brent 变体（注释 common.h:16-17，”灵感来自 Lua 的 ltable”）：插入时（common.c:177-232）若占位者在自己的主位置，把新者接到该链上；若占位者是从别处挤来的，把它驱逐到空槽、把主位置给新者。这让链短、多数查找命中主位置。

哈希：整数键 upb_inthash（common.c:88-96）在 64 位上把高 32 位异或折进低 32 位，廉价；字符串键用 Wyhash（ABSL 衍生，common.c:432-509），种子混入一个进程级 ASLR 派生种子 _upb_Seed（common.c:520-531）以随机化迭代序、防止测试依赖顺序。

注：hash/common.h:17 的顶部注释仍写着 “MurmurHash”，但实现（common.c:432-518）已是 Wyhash——注释过时。

负载因子 / 重哈希：isfull 在 0.875（size - size>>3）触发（common.c:102-106）；满则分配双倍大小的新表并重插全部存活项（common.c:592-599、:815-834）。字符串键存为长度前缀拷贝 upb_SizePrefixString（common.h:104-107、common.c:366-379）。

整数键”数组部分”在此版本已移除：upb_inttable（hash/int_table.h:20-22）现在只是 { upb_table t; }，稠密整数键不再有独立数组快路径——一切走哈希表。这是与旧 upb 资料的主要差异。

5. map_sorter：确定性输出

设 kUpb_EncodeOption_Deterministic 时，encode_map（encoder.c:602-611）改走排序器，而非随机序的哈希表迭代。因为 map 可嵌套，排序器是一个栈（message/internal/map_sorter.h:33-47）：_upb_mapsorter { entries; size; cap; }，每个 _upb_sortedmap { start; pos; end; } 是这个共享栈上的一个窗口。

_upb_mapsorter_pushmap（map_sorter.c:125-155）：把非空 upb_tabent 的指针拷进窗口（:142-147）——排序的是指针、不动活表；再按键类型 qsort（整数 :28-34、字符串经 compar[] 分派表 :85-105）。弹栈只是把 size 重置回窗口 start（map_sorter.h:84-87）——栈式 pop、无 free。扩展也用同样手法按字段号排序（map_sorter.c:157-185）。

6. 本章小结

机制 出处
“倒着写以避免预算长度” wire/encode.c:8
upb_encstate / upb_BackAlloc encoder.h:34-41、back_alloc.h:24-28
reserve / grow（偷 arena、右端 memcpy） encoder.c:96-102、back_alloc.c:94-109
逆字段序遍历 encoder.c:796-804
单字节 varint / ARM64 汇编 varint encoder.c:271-280、:155-240
子消息：payload→length→tag 前置 encoder.c:434-450
encode_message 自测量 size encoder.c:761-809
upb_Array tagged 指针 + lg2 message/internal/array.h:30-65
容量倍增 message/array.c:160-185
定长 packed 单次 memcpy encoder.c:336-367
upb_Map 结构 + 选表 message/internal/map.h:38-47、map.c:179-195
upb_tabent + next 哨兵 hash/common.h:125-159
Brent 变体插入 hash/common.c:177-232
整数/字符串哈希（Wyhash + ASLR 种子） hash/common.c:88-96、:432-531
0.875 负载因子 + 双倍重哈希 hash/common.c:102-106、:592-599
inttable 无数组部分 hash/int_table.h:20-22
map 排序器栈 message/internal/map_sorter.h:33-47、map_sorter.c:125-155

本站访问量

This site uses Just the Docs, a documentation theme for Jekyll.