本文档介绍了组件检查文件格式(检查格式)。
使用检查格式设置格式的文件称为检查文件,其文件扩展名通常为 .inspect
。
有关如何更改格式的信息。请参阅扩展 Inspect 文件格式。
概览
通过组件检查,组件能够在运行时公开有关其状态的结构化分层信息。
组件会使用检查格式来托管一个映射的虚拟内存对象 (VMO),以公开包含此内部状态的检查层次结构。
Inspect 层次结构由包含类型化 Properties 的嵌套 Node 组成。
目标
本文档中所述的“检查格式”具有以下目标:
低开销的数据更改
“检查文件格式”允许就地更改数据。例如,递增整数的开销大约是 2 个原子增量。
支持非静态层次结构
存储在检查文件中的层次结构可以在运行时修改。您随时可以在层次结构中添加或移除子项。这样,层次结构可以准确地表示组件工作集中对象的层次结构。
单写入器、多读取器并发,无需显式同步
与写入器同时操作的读取器会映射 VMO 并尝试截取数据快照。写入者会指明位于关键区段,但生成计数器无需与读取器进行显式同步。读取器使用生成计数器来确定 VMO 的快照何时一致且可以安全读取。
在组件终止后数据可能仍然可用
即使在写入组件终止后,读取器也可能保留包含检查数据的 VMO 的句柄。
术语
本部分定义了本文档中使用的常用术语。
- Inspect File - 使用本文档中所述的格式的有界限字节序列。
- 检查 VMO - 存储在虚拟内存对象 (VMO) 中的检查文件。
- 块 - 检查文件的适当大小的部分。块具有索引和顺序。
- 索引 - 特定块的唯一标识符。
byte_offset = index * 16
- Order - 以相对于最小大小的位偏移的形式给定的块的大小。
size_in_bytes = 16 << order
。根据块的大小(二的幂)将其分为类。 - 节点 - 层次结构中的已命名值,其他值可嵌套在此值下。在层次结构中,只有节点可以作为父级。
- 属性 - 包含类型化数据(例如字符串、整数等)的命名值。
- 层次结构 - 节点树,从单个“根”节点降序排列,每个“根”节点可能都包含属性。一个检查文件只包含一个层次结构。
本文档使用 RFC 2119 中定义的“必须”“应”/“建议”和“可以”关键字
所有位字段图都按小端字节序存储。
版本
当前版本:2
- 版本 2 允许值的名称为 NAME 或 STRING_REFERENCE。
组成块
检查文件会拆分为多个 Blocks
,其大小必须是 2 的幂。
最小块大小必须为 16 字节 (MIN_BLOCK_SIZE
),最大块大小必须是 16 字节的倍数。建议实现人员指定的块大小上限为小于页面大小(通常为 4096 字节)。在我们的参考实现中,最大块大小为 2048 字节 (MAX_BLOCK_SIZE
)。
所有块必须在 16 字节边界上对齐,并且在 VMO 中的寻址则根据索引指定,即指定 16 字节的偏移量 (offset =
index * 16
)。
我们使用 24 位作为索引,因此 Inspect Files 的大小可能最大为 256MiB。
block_header
由 16 个字节组成,如下所示:
.---------------------------------------------------------------.
| |1|1|1|1|1|2|2|2|2|2|3|3|3|3|3|4|4|4|4|4|5|5|5|5|5|6|6|
|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|
|---+---+-------+-----------------------------------------------|
| O | R | Type | |
|---------------------------------------------------------------|
| |
'---------------------------------------------------------------'
O = Order
R = Reserved, must be 0
The rest (left blank) depends on the payload
每个块都有一个 order
来指定其大小。
如果最大块大小为 2048 字节,则有 8 种可能的块顺序 (NUM_ORDERS
),编号为 0 到 7,分别对应大小为 16、32、64、128、256、512、1024 和 2048 字节的块。
每个块还都有一个类型,用于确定如何解译块中的其余字节。
好友分配
这种块布局允许使用好友分配功能高效分配块。我们推荐使用 Buddy 分配策略,但对于使用检查格式,则不要求这样做。
类型
所有支持的类型都在 //zircon/system/ulib/inspect/include/lib/inspect/cpp/vmo/block.h 中定义,具体类别如下:
枚举 | value | 类型名称 | 类别 |
---|---|---|---|
kFree |
0 | FREE |
内部 |
kReserved |
1 | RESERVED |
内部 |
kHeader |
2 | HEADER |
标题 |
kNodeValue |
3 | NODE_VALUE |
值 |
kIntValue |
4 | INT_VALUE |
值 |
kUintValue |
5 | UINT_VALUE |
值 |
kDoubleValue |
6 | DOUBLE_VALUE |
值 |
kBufferValue |
7 | BUFFER_VALUE |
值 |
kExtent |
8 | EXTENT |
范围 |
kName |
9 | NAME |
名称 |
kTombstone |
10 | TOMBSTONE |
值 |
kArrayValue |
11 | ARRAY_VALUE |
值 |
kLinkValue |
12 | LINK_VALUE |
值 |
kBoolValue |
13 | BOOL_VALUE |
值 |
kStringReference |
14 | STRING_REFERENCE |
参考文档 |
内部 - 这些类型用于实现块分配,读取器必须忽略它们。
Header - 此类型允许读取器检测检查文件以及有关快照一致性的原因。此块必须存在于索引 0 处。
值 - 这些类型直接显示在层次结构中。值必须具有名称和父级(必须为
NODE_VALUE
)。Extent - 此类型用于存储可能不适合单个块的长二进制数据。
名称 - 此类型存储适合单个块的二进制数据,通常用于存储值的名称。
Reference - 此类型包含单个规范值,其他块可以引用该值。
每种类型以不同的方式解读载荷,如下所示:
- 免费
- 已预订
- 标题
- 通用 VALUE 字段
- NODE_VALUE
- INT_VALUE
- UINT_VALUE
- DOUBLE_VALUE
- BUFFER_VALUE
- EXTENT
- 名称
- TOMBSTONE
- ARRAY_VALUE
- 链接
- BOOL_VALUE
- STRING_REFERENCE
免费
.---------------------------------------------------------------.
| |1|1|1|1|1|2|2|2|2|2|3|3|3|3|3|4|4|4|4|4|5|5|5|5|5|6|6|
|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|
|---+---+-------+-----------------------+-----------------------|
| O | R | Type | Next free block | |
|---------------------------------------------------------------|
| |
'---------------------------------------------------------------'
O = Order
R = Reserved, must be 0
Type = 0
Next free block = index (optional)
FREE
块可供分配。重要的是,零值块(16 个字节的 \0
)会被解释为 0 阶的 FREE
块,因此可以只需将缓冲区清零,以释放所有块。
写入器实现可以出于任何目的使用 FREE
块 8..63 中的未使用位。写入器实现必须将所有其他未使用的位设置为 0。
建议写入者使用上面指定的位置存储相同顺序的下一个空闲块的索引。使用此字段,可用块可以创建每个大小的可用块的单链接列表,以实现快速分配。当 NextFreeBlock 指向某个位置不是 FREE
或顺序不相同(通常是索引 0 处的 Header 块)时,会到达列表末尾。
已预订
.---------------------------------------------------------------.
| |1|1|1|1|1|2|2|2|2|2|3|3|3|3|3|4|4|4|4|4|5|5|5|5|5|6|6|
|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|
|---+---+-------+-----------------------------------------------|
| O | R | Type | |
|---------------------------------------------------------------|
| |
'---------------------------------------------------------------'
O = Order
R = Reserved, must be 0
Type = 1
RESERVED
块只需更改为其他类型即可。它是块分配与设置其类型之间的可选过渡状态,这对于实现正确性检查(确保即将使用的块不会被视为可用块)很有用。
标题
.---------------------------------------------------------------.
| |1|1|1|1|1|2|2|2|2|2|3|3|3|3|3|4|4|4|4|4|5|5|5|5|5|6|6|
|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|
|---+---+-------+---------------+-------------------------------|
| O | R | Type | Version | Magic number |
|---------------------------------------------------------------|
| Generation count |
|-------------------------------+-------------------------------|
| Size in bytes | Unused |
|---------------------------------------------------------------|
| |
'---------------------------------------------------------------'
O = Order
R = Reserved, must be 0
Type = 2
Version = 2
Magic number = "INSP"
文件开头必须有一个 HEADER
代码块。它包括一个魔数(“INSP”)、版本(当前为 2)、生成数(用于并发控制部分的虚拟机大小)以及标头的第一个字节不得为有效的 ASCII 字符。
如需了解必须如何使用世代计数实现并发控制,请参阅下一部分。
NODE_VALUE 和 TOMBSTONE
.---------------------------------------------------------------.
| |1|1|1|1|1|2|2|2|2|2|3|3|3|3|3|4|4|4|4|4|5|5|5|5|5|6|6|
|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|
|---+---+-------+-----------------------+-----------------------|
| O | R | Type | Parent index | Name index |
|---------------------------------------------------------------|
| Reference count (optional) |
'---------------------------------------------------------------'
O = Order
R = Reserved, must be 0
Type = {3,10}
节点是用于进一步嵌套的定位点,值的 ParentID
字段只能引用 NODE_VALUE
类型的块。
NODE_VALUE
块支持可选的引用计数和 Tombstoning,以允许高效的实现,如下所示:
Refcount
字段可能包含引用给定 NODE_VALUE
作为父级的值的数量。删除后,NODE_VALUE
会成为一个名为 TOMBSTONE
的新特殊类型。只有当 TOMBSTONE
的 Refcount
为 0 时,系统才会将其删除。
这样一来,无需明确跟踪节点的子项的写入器实现即可,并且可以防止出现以下情况:
// "b" has a parent "a"
Index | Value
0 | HEADER
1 | NODE "a", parent 0
2 | NODE "b", parent 1
/* delete "a", allocate "c" as a child of "b" which reuses index 1 */
// "b"'s parent is now suddenly "c", introducing a cycle!
Index | Value
0 | HEADER
1 | NODE "c", parent 2
2 | NODE "b", parent 1
{INT,UINT,DOUBLE,BOOL}_VALUE
.---------------------------------------------------------------.
| |1|1|1|1|1|2|2|2|2|2|3|3|3|3|3|4|4|4|4|4|5|5|5|5|5|6|6|
|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|
|---+---+-------+-----------------------+-----------------------|
| O | R | Type | Parent index | Name index |
|---------------------------------------------------------------|
| Inlined numeric value |
'---------------------------------------------------------------'
O = Order
R = Reserved, must be 0
Type = {4,5,6,13}
数字 VALUE
块都包含内嵌在块的第二个 8 个字节中的 64 位数字类型。
BUFFER_VALUE
.---------------------------------------------------------------.
| |1|1|1|1|1|2|2|2|2|2|3|3|3|3|3|4|4|4|4|4|5|5|5|5|5|6|6|
|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|
|---+---+-------+-----------------------+-----------------------|
| O | R | Type | Parent index | Name index |
|---------------------------------------------------------------|
| Total length | Extent index | F |
'---------------------------------------------------------------'
O = Order
R = Reserved, must be 0
Type = 7
Total length = size of the buffer
Extent index = index of the first extent containing bytes for the buffer
F = Display format {0,1}
常规 BUFFER_VALUE
块在一个或多个关联的 EXTENT
块中引用任意字节数据。
BUFFER_VALUE
块包含保存二进制数据的第一个 EXTENT
块的索引,并且它们包含所有区间的数据总长度(以字节为单位)。
格式标志指定应如何解译字节数据,如下所示:
枚举 | 值 | 含义 |
---|---|---|
kUtf8 | 0 | 字节数据可解释为 UTF-8 字符串。 |
kBinary | 1 | 字节数据是任意二进制数据,可能无法打印。 |
分界线
.---------------------------------------------------------------.
| |1|1|1|1|1|2|2|2|2|2|3|3|3|3|3|4|4|4|4|4|5|5|5|5|5|6|6|
|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|
|---+---+-------+-----------------------+-----------------------|
| O | R | Type | Next extent index | R |
|---------------------------------------------------------------|
| Payload |
'---------------------------------------------------------------'
O = Order
R = Reserved, must be 0
Type = 8
Next extent index = index of next extent in the chain
Extent index = index of the extent containing bytes for the string
Payload = byte data payload up to at most the end of the block. Size
depends on the order
EXTENT
块包含任意字节数据载荷以及链中下一个 EXTENT
的索引。通过按顺序读取每个 EXTENT
直到读取总长度字节,可以检索缓冲区值的字节数据。
姓名
.---------------------------------------------------------------.
| |1|1|1|1|1|2|2|2|2|2|3|3|3|3|3|4|4|4|4|4|5|5|5|5|5|6|6|
|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|
|---+---+-------+-----------------------------------------------|
| O | R | Type | Length | Reserved |
|---------------------------------------------------------------|
| Payload |
'---------------------------------------------------------------'
O = Order
R = Reserved, must be 0
Type = 9
Payload = contents of the name. Size depends on the order
NAME
块为对象和值提供人类可读的标识符。它们由完全适合指定分块的 UTF-8 载荷组成。
STRING_REFERENCE
.---------------------------------------------------------------.
| |1|1|1|1|1|2|2|2|2|2|3|3|3|3|3|4|4|4|4|4|5|5|5|5|5|6|6|
|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|
|---+---+-------+-----------------------+-----------------------|
| O | R | Type | Next Extent Index | Reference Count |
|---------------------------------------------------------------|
| Total length | Payload |
'---------------------------------------------------------------'
O = Order
R = Reserved
Type = 14
Next Extent Index = index of the first overflow EXTENT, or 0 if Payload does not overflow
Reference Count = number of references to this STRING_REFERENCE
Total length = size of the Payload in bytes. Payload overflows into Next Extent if
Total length > ((16 << Order) - 12)
Payload = the canonical instance of a string. The size of the Payload field depends on the
Order. If the size of the Payload + 12 is greater than 16 << Order, then the Payload
is too large to fit in one block and will overflow into Next Extent
STRING_REFERENCE
块用于在 VMO 中实现具有引用语义的字符串。它们是 EXTENT
链接列表的开头,这意味着它们的值不受限制。在预期使用 NAME
的位置可以使用 STRING_REFERENCE
块。
ARRAY_VALUE
.---------------------------------------------------------------.
| |1|1|1|1|1|2|2|2|2|2|3|3|3|3|3|4|4|4|4|4|5|5|5|5|5|6|6|
|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|
|---+---+-------+-----------------------+-----------------------|
| O | R | Type | Parent index | Name index |
|---------------------------------------------------------------|
| T | F | Count | Reserved |
|---------------------------------------------------------------|
| Payload |
'---------------------------------------------------------------'
O = Order
R = Reserved, must be 0
Type = 11
T = Type of the stored values {4,5,6,14}
F = Display format {0,1,2}
Count = Count of stored values
Payload = array of size |count|
ARRAY_VALUE
块 Payload
的格式取决于存储值类型 T
,其解释方式与 Type 字段完全相同。当 T ∊ {4, 5, 6}
时,Payload
应是按字节边界打包的 64 位数值。当 T ∊ {14}
时,Payload
应由 32 位值组成,表示 T
类型的块的 24 位索引,这些值沿字节边界打包在一起。在本例中,只允许使用平面数组 F = 0
。
当为 F = 0
时,ARRAY_VALUE
应默认实例化。对于数字,这应该是相关的零值。在字符串情况下,这应是空字符串,由特殊值 0
指示。
给定“存储值类型”(或其索引)的 Count 个条目(或其索引)出现在块中偏移量 16 处。
显示格式字段用于影响数组的显示方式,其解释如下:
枚举 | 值 | 说明 |
---|---|---|
kFlat | 0 | 显示为有序的平面数组,没有其他格式。 |
kLinearHistogram | 1 | 将前两个条目解释为线性直方图的 floor 和 step_size 参数,定义如下。 |
kExponentialHistogram | 2 | 对于指数直方图,将前三个条目解读为 floor 、initial_step 和 step_multiplier ,定义如下。 |
线性直方图
该数组是一个线性直方图,以内嵌方式存储其参数,并包含上溢和下溢存储分区。
前两个元素分别是参数 floor
和 step_size
(如下文中所定义)。
存储分区数 (N) 隐式为 Count - 4
。
其余元素为存储分区:
2: (-inf, floor),
3: [floor, floor+step_size),
i+3: [floor + step_size*i, floor + step_size*(i+1)),
...
N+3: [floor+step_size*N, +inf)
指数直方图
该数组是一个指数直方图,以内嵌方式存储其参数,并且同时包含上溢和下溢存储分区。
前三个元素分别是参数 floor
、initial_step
和 step_multiplier
(如下文中所定义)。
存储分区数 (N) 隐式计数为 5。
其余为存储分区:
3: (-inf, floor),
4: [floor, floor+initial_step),
i+4: [floor + initial_step * step_multiplier^i, floor + initial_step * step_multiplier^(i+1))
N+4: [floor + initial_step * step_multiplier^N, +inf)
LINK_VALUE
.---------------------------------------------------------------.
| |1|1|1|1|1|2|2|2|2|2|3|3|3|3|3|4|4|4|4|4|5|5|5|5|5|6|6|
|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|4|6|8|0|2|
|---+---+-------+-----------------------------------------------|
| O | R | Type | Parent index | Name index |
|---------------------------------------------------------------|
| Content index | | F |
'---------------------------------------------------------------'
O = Order
R = Reserved, must be 0
Type = 12
Parent index = Index of the parent block
Name index = Index of the name of this value
Content index = Index of the content of this link (as a NAME node)
F = Disposition flags {0,1}
LINK_VALUE
块允许节点支持单独检查文件中存在的子项。
内容索引指定另一个 NAME
块,其内容是引用另一个检查文件的唯一标识符。读取器应通过目录读取或其他接口获取一系列 (Identifier, File)
对,并且可能会尝试使用存储的标识符将树拼接在一起,以便追踪链接。
Disposition Flags 指示读者如何接合树,如下所示:
枚举 | 值 | 说明 |
---|---|---|
kChildDisposition | 0 | 存储在关联文件中的层次结构应该是 LINK_VALUE 父级的子级。 |
kInlineDisposition | 1 | 应将存储在关联文件中的根目录的子级和属性添加到 LINK_VALUE 的父级。 |
例如:
// root.inspect
root:
int_value = 10
child = LINK("other.inspect")
// other.inspect
root:
test = "Hello World"
next:
value = 0
// kChildDisposition produces:
root:
int_value = 10
child:
test = "Hello World"
next:
value = 0
// kInlineDisposition produces:
root:
int_value = 10
test = "Hello World"
next:
value = 0
如果 Node 与其内嵌链接的子项添加的值之间的子项名称冲突,优先级由读取器定义。不过,大多数读取器会发现让关联的值优先考虑很有用,这样它们可以替换原始值。
并发控制
写入者必须使用全局版本计数器,以便读取器可以检测读取之间的运行中修改和修改,而无需与写入器进行通信。这支持单写入器多读取器并发。
该策略适用于写入者在开始和结束写入操作时递增全局生成计数器。
这是一种简单的策略,具有显著的优势:在递增开始写入和结束写入的版本号之间,写入器可以对缓冲区执行任意数量的操作,而无需考虑数据更新的原子性。
主要缺点是,由于频繁更新 writer,读取可能会无限期延迟,但读取器可以在实践中采取缓解措施。
阅读器算法
读取者使用以下算法获取检查 VMO 的一致快照:
- 自锁,直到版本号为偶数(无并发写入),
- 复制整个 VMO 缓冲区,并
- 检查缓冲区中的版本号是否与第 1 步中的版本号相一致。
只要版本号匹配,客户端就可以读取其本地副本来构建共享状态。 如果版本号不匹配,客户端可能会重试整个进程。
写入者锁定算法
写入者可通过执行以下操作来锁定检查 VMO 以进行修改:
atomically_increment(generation_counter, acquire_ordering);
这通过将世代设置为奇数来锁定文件,防止并发读取。获取排序可确保在进行此变更之前不会对加载进行重新排序。
写入者解锁算法
写入者可通过执行以下操作,在修改后解锁检查 VMO:
atomically_increment(generation_counter, release_ordering);
通过将世代设置为新的偶数来解锁允许并发读取的文件。版本排序可确保对文件的写入在生成数更新之前可见。