用有序页集合协调 TCG 代码失效时的加锁
QEMU 在 TCG 页集合中使用 AVL 型 QTree，按页号去重并在竞争时按顺序重新获取页锁。
工程问题#
使一段物理内存对应的 Translation Block 失效时，还可能遇到跨页 TB 引入的新页面。页集合在遍历过程中增长，既要避免同一页重复加锁，也要避免多个执行线程以相反顺序阻塞等待页锁。
实际实现#
page_collection 用页号比较函数构造 QTree。查找依据比较结果进入左、右子树；插入维护左右子树高度差，并在失衡时旋转。收集页时先去重，递增页号可以直接加锁，遇到更小页号则尝试非阻塞加锁；失败后释放已有锁，再以树的有序遍历重新获取。
处理流程#
- 为此次失效操作建立以页号为键的 QTree
- 查找待加入页面，已存在则复用集合条目
- 插入新页；高度差超出允许范围时执行单旋或双旋
- 乱序 trylock 失败时释放已有锁，按页号顺序遍历并重试
- 完成 TB 失效后销毁集合，由条目清理函数解锁并释放内存
源码片段#
固定版本 · 原文摘录547 */548static bool page_trylock_add(struct page_collection *set, tb_page_addr_t addr)549{550 tb_page_addr_t index = addr >> TARGET_PAGE_BITS;551 struct page_entry *pe;552 PageDesc *pd;553554 pe = q_tree_lookup(set->tree, &index);555 if (pe) {556 return false;557 }558559 pd = page_find(index);560 if (pd == NULL) {561 return false;562 }563564 pe = page_entry_new(pd, index);565 q_tree_insert(set->tree, &pe->index, pe);将物理地址换成页号，先在 QTree 查重，再为新页面建立条目；该树维护实际需要加锁的页面集合。
601static struct page_collection *page_collection_lock(tb_page_addr_t start,602 tb_page_addr_t last)603{604 struct page_collection *set = g_malloc(sizeof(*set));605 tb_page_addr_t index;606 PageDesc *pd;607608 start >>= TARGET_PAGE_BITS;609 last >>= TARGET_PAGE_BITS;610 g_assert(start <= last);611612 set->tree = q_tree_new_full(tb_page_addr_cmp, NULL, NULL,613 page_entry_destroy);614 set->max = NULL;615 assert_no_pages_locked();616617 retry:618 q_tree_foreach(set->tree, page_entry_lock, NULL);619620 for (index = start; index <= last; index++) {用页号比较函数建立树，并在 retry 入口通过有序遍历获取已有页面的锁。
628 if (page_trylock_add(set, index << TARGET_PAGE_BITS)) {629 q_tree_foreach(set->tree, page_entry_unlock, NULL);630 goto retry;631 }632 assert_page_locked(pd);633 PAGE_FOR_EACH_TB(unused, unused, pd, tb, n) {634 if (page_trylock_add(set, tb_page_addr0(tb)) ||635 (tb_page_addr1(tb) != -1 &&636 page_trylock_add(set, tb_page_addr1(tb)))) {637 /* drop all locks, and reacquire in order */638 q_tree_foreach(set->tree, page_entry_unlock, NULL);639 goto retry;640 }收集当前页及跨页 TB 的相关页；遇到不能立即获取的页锁就释放已有锁，再回到有序获取流程。
1197 while (1) {1198 cmp = tree->key_compare(key, node->key, tree->key_compare_data);1199 if (cmp == 0) {1200 return node;1201 } else if (cmp < 0) {1202 if (!node->left_child) {1203 return NULL;1204 }12051206 node = node->left;1207 } else {1208 if (!node->right_child) {1209 return NULL;1210 }12111212 node = node->right;1213 }1214 }1215}比较结果为负进入左孩子，为正进入右孩子，相等返回当前节点。这直接展示页号二叉搜索树的查找约束。
1167static QTreeNode *1168q_tree_node_balance(QTreeNode *node)1169{1170 if (node->balance < -1) {1171 if (node->left->balance > 0) {1172 node->left = q_tree_node_rotate_left(node->left);1173 }1174 node = q_tree_node_rotate_right(node);1175 } else if (node->balance > 1) {1176 if (node->right->balance < 0) {1177 node->right = q_tree_node_rotate_right(node->right);1178 }1179 node = q_tree_node_rotate_left(node);1180 }11811182 return node;1183}高度差小于 -1 或大于 1 时执行旋转；孩子的倾斜方向决定先转孩子还是直接转当前节点，分别对应 AVL 的双旋和单旋。
片段包含实际加锁入口、失败重试、BST 比较路径及 AVL 旋转。left_child / right_child 用来区分真实孩子和遍历线索，查找时必须检查这些标志。
收益与取舍#
工程分析带来的收益
- 二叉搜索树的键顺序同时支撑成员查找与有序遍历，不必维护两份页集合
- AVL 平衡避免连续递增页号把搜索树退化为链；有序重试为动态扩大的锁集合提供一致获取顺序
付出的代价
- 每次临时集合的插入要维护指针和高度差，比仅做哈希去重复杂
- QTree 不替代锁协议：乱序页只能先 trylock，竞争失败后可能释放并重新获取多个锁
可比较的选择
哈希集合加排序后的页号数组可以完成去重和有序加锁，但发现新的跨页 TB 页面时需要更新数组或重新排序。
版本与适用范围#
对应 QEMU v9.2.0 系统模拟 TCG 的 tb_invalidate_phys_range / page_collection_lock。此处 QTree 来自 QEMU 保存的 GLib 树实现，通过高度差和旋转实现 AVL 平衡；不是 Linux KVM 页表，也不是全部 QEMU 内存映射的索引。
参考来源#
源码、官方文档与原始论文相关实现与比较#
1 个相关案例每个 easy handle 可有多种内部期限，但全局伸展树只保留它最近的一项，为 Multi 接口汇总下一次唤醒时间。