在 NFS ACL 转换后排列用户与组条目
Linux NFS 服务端转换访问控制列表后，用原地冒泡排序分别按 UID、GID 排列命名用户和组条目。
工程问题#
NFSv4 ACL 转成 POSIX ACL 后，代码会分别把命名用户和组条目整理为 UID、GID 升序。排序对象通常较短，同时必须保留 owner、group owner、mask 等结构性条目的位置。
实际实现#
nfs4_acl_nfsv4_to_posix 生成访问 ACL 和默认 ACL 后调用 sort_pacl。它只取连续的 ACL_USER、ACL_GROUP 区段分别排序；sort_pacl_range 反复比较相邻条目，逆序就交换，一趟没有交换即结束。比较函数在相同标签内按内核 UID 或 GID 比较。
处理流程#
- 将 NFSv4 权限状态转换成访问 ACL 与默认 ACL
- 分别定位命名用户和命名组的连续条目区段
- 按 UID 或 GID 比较相邻条目并交换逆序对
- 继续扫描，直到完整一趟没有发生交换
源码片段#
固定版本 · 原文摘录753 *pacl = posix_state_to_acl(&effective_acl_state, flags);754 if (IS_ERR(*pacl)) {755 ret = PTR_ERR(*pacl);756 *pacl = NULL;757 goto out_dstate;758 }759 *dpacl = posix_state_to_acl(&default_acl_state,760 flags | NFS4_ACL_TYPE_DEFAULT);761 if (IS_ERR(*dpacl)) {762 ret = PTR_ERR(*dpacl);763 *dpacl = NULL;764 posix_acl_release(*pacl);765 *pacl = NULL;766 goto out_dstate;767 }768 sort_pacl(*pacl);769 sort_pacl(*dpacl);770 ret = 0;成功生成访问 ACL 和默认 ACL 后才分别排序；错误分支会释放或清空已生成对象。
394sort_pacl(struct posix_acl *pacl)395{396 /* posix_acl_valid requires that users and groups be in order397 * by uid/gid. */398 int i, j;399400 /* no users or groups */401 if (!pacl || pacl->a_count <= 4)402 return;403404 i = 1;405 while (pacl->a_entries[i].e_tag == ACL_USER)406 i++;407 sort_pacl_range(pacl, 1, i-1);408409 BUG_ON(pacl->a_entries[i].e_tag != ACL_GROUP_OBJ);410 j = ++i;411 while (pacl->a_entries[j].e_tag == ACL_GROUP)412 j++;413 sort_pacl_range(pacl, i, j-1);414 return;只排序 ACL_USER 与 ACL_GROUP 区段，分别按 UID、GID 升序排列，其他结构性条目保留原位。注释提到的校验要求需要结合相同版本的校验器核对。
374static void375sort_pacl_range(struct posix_acl *pacl, int start, int end) {376 int sorted = 0, i;377378 /* We just do a bubble sort; easy to do in place, and we're not379 * expecting acl's to be long enough to justify anything more. */380 while (!sorted) {381 sorted = 1;382 for (i = start; i < end; i++) {383 if (pace_gt(&pacl->a_entries[i],384 &pacl->a_entries[i+1])) {385 sorted = 0;386 swap(pacl->a_entries[i],387 pacl->a_entries[i + 1]);388 }389 }390 }391}相邻逆序交换，整趟无交换终止；原文注释直接说明选择冒泡排序的短列表和原地实现前提。
362static bool363pace_gt(struct posix_acl_entry *pace1, struct posix_acl_entry *pace2)364{365 if (pace1->e_tag != pace2->e_tag)366 return pace1->e_tag > pace2->e_tag;367 if (pace1->e_tag == ACL_USER)368 return uid_gt(pace1->e_uid, pace2->e_uid);369 if (pace1->e_tag == ACL_GROUP)370 return gid_gt(pace1->e_gid, pace2->e_gid);371 return false;372}同一用户或组区段分别用 uid_gt、gid_gt 比较；只有严格逆序才交换，相同键不交换。
摘录包括转换后的调用点、子区段选择、冒泡循环及比较规则。文件头采用 BSD 三条款许可。
收益与取舍#
工程分析带来的收益
- 排序原地完成，只交换已有 ACL 条目，不额外分配与条目数成比例的缓冲区
- 源码明确以列表较短和实现简单作为选择理由；已排序区段一趟即可结束
付出的代价
- 一般最坏时间为 O(n²)，不适合不受限制的大列表；该版本每趟都扫描完整区段，没有缩短尾部边界
- 排序只调整位置，不负责把不支持的 NFSv4 权限语义变成可表示的 POSIX ACL，转换及校验仍可能失败
可比较的选择
原地插入排序同样适合短列表且可保持稳定，但通过移动一段条目插入当前项；不能仅凭渐进复杂度判断哪个在此调用点更快。
通用 O(n log n) 排序更适合较长列表，但需要额外的比较器适配；这里没有提供与通用排序的性能对比数据。
版本与适用范围#
对应 Linux v6.12 fs/nfsd/nfs4acl.c。仅排序转换后的命名用户、命名组区段，不改变整个 NFSv4 ACE 序列的授权语义。这里的“列表较短”来自上游设计注释，不是对所有请求长度的数值上限承诺。源文件旧注释称 posix_acl_valid 要求 ID 有序，但 v6.12 的该校验器没有比较前后 UID/GID；不能据此声称乱序输入一定会被它拒绝。