对实体查询在 LongAVLTreeSet.Subset 引发 IllegalArgumentException 的分析

发表于 阅读次数： 本文字数： 2.4k 阅读时长 ≈ 4 分钟

日常运维 OSTC，发现有服务端崩溃现象。瞅了眼 crash-report 文件夹，看到了如下的崩溃日志

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
---- Minecraft Crash Report ----
// Don't do that.

Time: 2025-08-12 21:07:57
Description: Ticking entity

java.lang.IllegalArgumentException: Start element (9223367638808264704) is larger than end element (-9223372036854775808)
	at it.unimi.dsi.fastutil.longs.LongAVLTreeSet$Subset.<init>(LongAVLTreeSet.java:1080)
	at it.unimi.dsi.fastutil.longs.LongAVLTreeSet.subSet(LongAVLTreeSet.java:1047)
	at net.minecraft.class_5573.method_31777(class_5573.java:57)
	at net.minecraft.class_5573.method_31783(class_5573.java:122)

...

-- Entity being ticked --
Details:
	Entity Type: minecraft:arrow (net.minecraft.class_1667)
	Entity ID: 15871
	Entity Name: Arrow
	Entity's Exact location: 28.28, 90.00, 15.78
	Entity's Block location: World: (28,89,15), Section: (at 12,9,15 in 1,5,0; chunk contains blocks 16,0,0 to 31,255,15), Region: (0,0; contains chunks 0,0 to 31,31, blocks 0,0,0 to 511,255,511)
	Entity's Momentum: -98941291.49, -0.02, -50361527.12
	Entity's Passengers: []
	Entity's Vehicle: null
...

可发现，是一个超高速箭矢实体，在移动计算时，于 LongAVLTreeSet$Subset 里触发了 IllegalArgumentException 异常

是之前没见过的崩服场景，得分析一波

省流

summary

背景知识

简单提一下分析所涉及的一些背景知识，以便后续分析使用（主要是得讲清楚“区段坐标索引”这个概念）

下述分析均使用 yarn 1.21.1+build.1 作为反混淆表，并调整了下局部变量的命名

相关代码自 1.17 开始至今（1.21.8）都长得几乎一样，基本可以直接参考

区段

区段，或者说子区块，是一个 16x16x16 的范围概念

任意一个世界坐标 $(x, y, z)$ 归属的区段坐标 = $(\left\lfloor\frac{x}{16}\right\rfloor, \left\lfloor\frac{y}{16}\right\rfloor, \left\lfloor\frac{z}{16}\right\rfloor)$

查询范围实体

MC 里存在非常多的“查询一个长方体范围内的实体列表”的操作，如碰撞检测、活塞推实体、横扫攻击、矿车载客等

最简单的实现“查询范围实体”的方式，就是直接遍历一遍当前世界里的全部实体，挨个检查实体碰撞箱是否与给定范围相交，但这显然效率太低了

一种简单有效的实现，就是对 MC 这个三维世界进行分块处理，如将整个世界切成一个个 区段。 然后，给每个区段维护一份实体列表，储存着坐标位于此区段的实体。 在查询范围实体时，只需要找到与给定范围相交的那些区段，再遍历这些区段里的实体就行了，这样就无需检查那些坐标离得老远的实体了。

注：具体实现“找到与给定范围相交的那些区段”时，会扩大一些查询范围，以适配大碰撞箱的实体

区段坐标索引

为了高效地储存“给每个区段维护一份实体列表”的若干个区段级实体列表，需要搞一个“区段坐标” -> “实体列表”的映射表。 麻将考虑到区段坐标的取值并不会很大，于是把区段坐标映射成一个 64 位整数 long，然后把这个 long 作为映射表的索引

将区段坐标映射成整数索引的实现如下

1
2
3
4
5
6
7
8
// net.minecraft.util.math.ChunkSectionPos#asLong(int, int, int)
public static long asLong(int x, int y, int z) {
    long index = 0L;
    index |= (x & 4194303L) << 42;  // 取 x 的低 22 位，贴到 index 的最高 22 位上
    index |= (y & 1048575L) << 0;   // 取 y 的低 20 位，贴到 index 的最低 20 位上
    index |= (z & 4194303L) << 20;  // 取 z 的低 22 位，贴到 index 的中间 22 位上
    return index;
}

返回值 index 的 64 个 bit 的结构如下所示：

1
2
3
4
+---------------------+---------------------+--------------------+
|     x (22 bits)     |     z (22 bits)     |     y (20 bits)    |
+---------------------+---------------------+--------------------+
63 (High)           42 41                 20 19            (Low) 0

分析开始

先把堆栈跟踪搞映射到 yarn，好看些

1
2
3
4
5
6
7
8
9
10
11
12
java.lang.IllegalArgumentException: Start element (9223367638808264704) is larger than end element (-9223372036854775808)
	at it.unimi.dsi.fastutil.longs.LongAVLTreeSet$Subset.<init>(LongAVLTreeSet.java:1080)
	at it.unimi.dsi.fastutil.longs.LongAVLTreeSet.subSet(LongAVLTreeSet.java:1047)
	at net.minecraft.world.entity.SectionedEntityCache.forEachInBox(SectionedEntityCache.java:57)
	at net.minecraft.world.entity.SectionedEntityCache.forEachIntersects(SectionedEntityCache.java:122)
	at net.minecraft.world.entity.SimpleEntityLookup.forEachIntersects(SimpleEntityLookup.java:43)
	at net.minecraft.world.World.getOtherEntities(World.java:695)
	at net.minecraft.entity.projectile.ProjectileEntity.shouldLeaveOwner(ProjectileEntity.java:125)
	at net.minecraft.entity.projectile.ProjectileEntity.tick(ProjectileEntity.java:116)
	at net.minecraft.entity.projectile.PersistentProjectileEntity.tick(PersistentProjectileEntity.java:173)
	at net.minecraft.entity.projectile.ArrowEntity.tick(ArrowEntity.java:74)
	at net.minecraft.server.world.ServerWorld.tickEntity(ServerWorld.java:770)

可发现，是查询世界指定范围内实体的 World.getOtherEntities 的调用发生了崩溃。这个调用栈看起来挺原版的，那可能大概率是原版的 bug

先重点观察 SectionedEntityCache.forEachInBox 这个调用 LongAVLTreeSet.subSet 的地方。代码和分析如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// net.minecraft.world.entity.SectionedEntityCache#forEachInBox
public void forEachInBox(Box box, LazyIterationConsumer<EntityTrackingSection<T>> consumer) {
    // 计算要查询的区段坐标的范围
    // 这里的 +-2.0 这种微调，是用来处理大体积碰撞箱实体。比如 2.0 就是因为目前水平最胖的实体恶魂的宽度是 4，4 / 2 = 2
    // ChunkSectionPos.getSectionCoord(x) 的结果等于 floor(x / 16)（向下取整）
    int sectionMinX = ChunkSectionPos.getSectionCoord(box.minX - 2.0);  // 查询的区段坐标范围的 X 下界
    int sectionMinY = ChunkSectionPos.getSectionCoord(box.minY - 4.0);  // 查询的区段坐标范围的 Y 下界
    int sectionMinZ = ChunkSectionPos.getSectionCoord(box.minZ - 2.0);  // 查询的区段坐标范围的 Z 下界
    int sectionMaxX = ChunkSectionPos.getSectionCoord(box.maxX + 2.0);  // 查询的区段坐标范围的 X 上界
    int sectionMaxY = ChunkSectionPos.getSectionCoord(box.maxY + 0.0);  // 查询的区段坐标范围的 Y 上界
    int sectionMaxZ = ChunkSectionPos.getSectionCoord(box.maxZ + 2.0);  // 查询的区段坐标范围的 Z 上界
    
    // 下面要遍历 (sectionMinX, sectionMinY, sectionMinZ) -> (sectionMaxX, sectionMaxY, sectionMaxZ) 这个区段坐标范围的所有区段

    for (int sectionX = sectionMinX; sectionX <= sectionMaxX; sectionX++) {  // 遍历区段坐标的 X
        // this.trackedPositions 是一个有序的 long 集合 LongAVLTreeSet，储存着所有含实体的区段坐标（通过 ChunkSectionPos.asLong 计算）
        // 下面这两行用于计算出满足 trackedPositions 里，所有区段 X 坐标等于 sectionX 的 index 的取值范围
        // 注意 ChunkSectionPos.asLong 返回值的结构，X 贡献的 bit 位于 index 的高位，Y,Z 的 bit 则位于低位，因此：
        //   把 Y,Z 的 bit 全部设置为 0，即可得到最小值 [x bits][42个0]
        //   将 Y,Z 的 bit 全部设置为 1，即可得到最大值 [x bits][42个1]
        long indexLower = ChunkSectionPos.asLong(sectionX, 0, 0);    // 获得 index 的最小值（闭区间）
        long indexUpper = ChunkSectionPos.asLong(sectionX, -1, -1);  // 获得 index 的最大值（闭区间）
        
        // 这一行代码在调用 subSet 时抛异常了
        LongIterator iter = this.trackedPositions.subSet(indexLower, indexUpper + 1).iterator();  // 这一行抛异常了

        // 遍历 longIterator，对可能的区段坐标执行后续操作
        while (iter.hasNext()) {
            long index = iter.nextLong();
            int sectionY = ChunkSectionPos.unpackY(index);
            int sectionZ = ChunkSectionPos.unpackZ(index);
            // ...
        }
    }
}

对于 LongAVLTreeSet.subSet 这个函数

1
2
// it.unimi.dsi.fastutil.longs.LongSortedSet#subSet(long, long)
LongSortedSet subSet(long fromElement, long toElement);

该函数是用来查询 [fromElement, toElement) 这个区间子集内的元素的。若 fromElement > toElement，就会因区间非法而抛出 IllegalArgumentException

这意味着，this.trackedPositions.subSet(indexLower, indexUpper + 1) 这个调用里，出现了 indexLower > indexUpper + 1 的非预期情况

重点观察这里 indexLower、indexUpper 计算方式

1
2
3
long indexLower = ChunkSectionPos.asLong(sectionX, 0, 0);    // 获得 index 的最小值（闭区间）
long indexUpper = ChunkSectionPos.asLong(sectionX, -1, -1);  // 获得 index 的最大值（闭区间）
LongIterator iter = this.trackedPositions.subSet(indexLower, indexUpper + 1).iterator();
1
2
3
4
+---------------------+---------------------+--------------------+
|     x (22 bits)     |     z (22 bits)     |     y (20 bits)    |
+---------------------+---------------------+--------------------+
63 (High)           42 41                 20 19            (Low) 0

重点来了。若 sectionX == 2097151 时，sectionX 的二进制表达将会是 21 个 1。此时会有

1
2
3
4
indexLower     == 0111111111111111111111000000000000000000000000000000000000000000  // [0][21 个 1][42 个 0]
indexUpper     == 0111111111111111111111111111111111111111111111111111111111111111  // [0][63 个 1]
indexUpper + 1 == 1000000000000000000000000000000000000000000000000000000000000000  // [1][63 个 0]
//                 [      21 bits      ][                 63 bits                ]

这里有：

  • indexUpper 的取值为 long 类型的最大值 Long.MAX_VALUE
  • indexUpper + 1 将发生有符号整数上溢，变成 long 类型的最小值 Long.MIN_VALUE，是一个负数
  • 此时将发生 indexLower > indexUpper + 1，触发 IllegalArgumentException 异常

触发条件

不难发现，要触发这一异常，sectionX 的二进制的低 22 位必须等于 2097151，也即 [0][21 个 1]，才能触发这个 bug。 这是因为只有这个时候，ChunkSectionPos.asLong(sectionX, -1, -1) 才能计算得到 Long.MAX_VALUE，最终 +1 上溢成负数。

因此，该 bug 的触发条件为：

$$sectionX\ \texttt{&} \ (2^{22}-1) = 2^{21}-1$$

这里 sectionX 表示区段坐标的 X 值， & 表示位运算取与

稍加变形，可得到：

$$sectionX\ \ mod\ \ 2^{22} = 2^{21}$$

或者

$$\left\lfloor\frac{x}{16}\right\rfloor\ \ mod\ \ 2^{22} = 2^{21}$$

若“查询范围实体”操作传入的范围涵盖了满足上述条件的区段时，则会触发此 bug

一些常见的取值，同时也是 sectionX 的绝对值最小的两个取值：

sectionX X 坐标范围
2097151 [33554416, 33554432)
-2097153 [-33554448, -33554432)

注意到这里 X 坐标范围已经是三千多万了，超过了三千万这个世界边境大小，是位于边境之外的

应该也正因如此，麻将才会如此设计，给 x 和 z 保留了 22 个 bit。不过这也不是可恶的麻将偷懒不做范围检查的借口。 有边界条件没问题，不处理边界条件就妥妥地是麻将的问题

由于这个坐标范围已经到了边境之外了，并且也远超出了边境范围，因此这个 bug 日常难以触发，基本只有在玩超高速实体时才会遇到，如：

  • 蓄力边境珍珠炮 / 箭炮
  • INF 速度的矿车 + 继承矿车速度的实体

影响范围

从 20w45a（1.17 快照）至今（1.21.8、25w37a）所有版本

注意一些优化 mod（如 1.17.1 的 Lithium 0.7.5）对实体移动的一些修改优化可能导致该 bug 无法被触发

修复

Carpet-TIS-Addition 在 v1.69.0 加了个规则 entityChunkSectionIndexXOverflowFix。把它设置成 true 就好了

后续也许可能会考虑做个独立的 fix mod，更轻量一些