JINHU
Resource Allocator (RA) 代码详细分析
整体架构概述
Resource Allocator 是一个通用的资源分配器,最初用于地址空间管理,但实际上可以管理任意的整数集合。
核心架构图
┌─────────────────────────────────────────────────────────────┐
│ RA_ARENA (资源竞技场) │
├─────────────────────────────────────────────────────────────┤
│ - 名称、量子大小、策略标志 │
│ - 导入/释放回调函数 │
│ - 锁机制 │
├─────────────────────────────────────────────────────────────┤
│ │
│ ┌────────────────┐ ┌──────────────────┐ │
│ │ Segment List │ │ Free Table │ │
│ │ (双向链表) │ │ (Splay Tree + │ │
│ │ │ │ Buckets) │ │
│ └────────────────┘ └──────────────────┘ │
│ │ │ │
│ │ │ │
│ ▼ ▼ │
│ ┌──────────────────────────────────┐ │
│ │ Boundary Tags (BT) │ │
│ │ - base: 资源基址 │ │
│ │ - uSize: 资源大小 │ │
│ │ - type: free/live │ │
│ │ - flags: 标志 │ │
│ └──────────────────────────────────┘ │
│ │
│ ┌────────────────┐ │
│ │ Segment Hash │ (快速查找已分配资源) │
│ └────────────────┘ │
└─────────────────────────────────────────────────────────────┘
核心数据结构
Boundary Tag (BT) 结构
struct _BT_ {
enum bt_type {
btt_free, /* 空闲资源段 */
btt_live /* 已分配资源段 */
} type;
unsigned int is_leftmost; /* 是否为导入区间的最左边 */
unsigned int is_rightmost; /* 是否为导入区间的最右边 */
unsigned int free_import; /* 是否可以释放导入 */
RA_BASE_T base; /* 资源基址 */
RA_LENGTH_T uSize; /* 资源大小 */
/* 双向有序链表 - 按地址排序的所有段 */
struct _BT_ *pNextSegment;
struct _BT_ *pPrevSegment;
/* 双向无序链表 - 相同标志的空闲段 */
struct _BT_ *next_free;
struct _BT_ *prev_free;
IMG_HANDLE hPriv; /* 用户私有数据 */
RA_FLAGS_T uFlags; /* 标志位 */
};
BT 生命周期图示
分配过程:
┌─────────┐ ┌─────────┐ ┌─────────┐
│ Free │ ───> │ Split │ ───> │ Live │
│ BT │ │ if │ │ BT │
│ │ │ needed │ │ │
└─────────┘ └─────────┘ └─────────┘
释放过程:
┌─────────┐ ┌─────────┐ ┌─────────┐
│ Live │ ───> │ Merge │ ───> │ Free │
│ BT │ │ with │ │ BT │
│ │ │Neighbors│ │ │
└─────────┘ └─────────┘ └─────────┘
Arena 结构
struct _RA_ARENA_ {
IMG_CHAR name[RA_MAX_NAME_LENGTH]; /* 竞技场名称 */
RA_LENGTH_T uQuantum; /* 量子大小(对齐粒度) */
/* 导入回调接口 */
union {
void* pImportAlloc;
PFN_RA_IMPORT_ALLOC_SINGLE pImportAllocSingle;
PFN_RA_IMPORT_ALLOC_MULTI pImportAllocMulti;
};
enum RA_IMPORT_ALLOC_METHOD eImportAllocMethod;
PFN_RA_IMPORT_FREE pImportFree;
void *pImportHandle; /* 导入句柄 */
IMG_PSPLAY_TREE per_flags_buckets; /* 按标志分类的桶 */
BT *pHeadSegment; /* 段链表头 */
HASH_TABLE *pSegmentHash; /* 段地址哈希表 */
POS_LOCK hLock; /* 锁 */
RA_POLICY_T ui32PolicyFlags; /* 策略标志 */
IMG_UINT32 ui32LockClass; /* 锁类 */
IMG_UINT64 ui64TotalArenaSize; /* 总大小 */
IMG_UINT64 ui64FreeArenaSize; /* 空闲大小 */
};
核心算法详解
Free Table 组织结构
Free Table 使用 Splay Tree + Bucket Array 的混合结构：
Splay Tree (按 flags 组织)
│
▼
┌──────────────────┐
│ Flags Bucket │
│ (flags=0x123) │
├──────────────────┤
│ buckets[0] ──> BT(size: 1~1)
│ buckets[1] ──> BT(size: 2~3)
│ buckets[2] ──> BT(size: 4~7)
│ buckets[3] ──> BT(size: 8~15)
│ buckets[4] ──> BT(size: 16~31)
│ ...
│ buckets[n] ──> BT(size: 2^n ~ 2^(n+1)-1)
└──────────────────┘
每个 bucket 内的 BT 链表:
buckets[n] ──> BT1 ──> BT2 ──> BT3 ──> NULL
// 对于大小为 uSize 的段,其桶索引为:
uIndex = pvr_log2(uSize); // floor(log2(uSize))
// 例如:
// size=5 ──> index=2 (bucket[2]: 4~7)
// size=16 ──> index=4 (bucket[4]: 16~31)
分配算法流程
RA_Alloc() 流程:
┌──────────────────────────────────────┐
│ 1. 参数验证与对齐 │
│ - 对齐到 Arena 量子大小 │
│ - 验证对齐要求(必须是2的幂) │
└──────────────────┬───────────────────┘
│
▼
┌──────────────────────────────────────┐
│ 2. _AttemptAllocAligned() │
│ 尝试从现有资源分配 │
└──────────────────┬───────────────────┘
│
┌─────────┴─────────┐
│ │
成功 │ │ 失败
▼ ▼
┌─────────┐ ┌──────────────────┐
│ 返回 │ │ 3. 导入新资源 │
│ 基址 │ │ _AttemptImportSpan│
└─────────┘ └────────┬──────────┘
│
▼
┌──────────────────┐
│ 4. 重试分配 │
│ _AttemptAlloc... │
└──────────────────┘
_AttemptAllocAligned 详细流程
static IMG_BOOL
_AttemptAllocAligned(RA_ARENA *pArena,
RA_LENGTH_T uSize,
RA_FLAGS_T uFlags,
RA_LENGTH_T uAlignment,
RA_BASE_T *base,
RA_PERISPAN_HANDLE *phPriv)
{
// 1. 查找匹配 flags 的 bucket
pArena->per_flags_buckets = PVRSRVSplay(uFlags, pArena->per_flags_buckets);
if (!bucket_found) return IMG_FALSE;
// 2. 计算搜索范围
index_low = pvr_log2(uSize);
if (uAlignment)
index_high = pvr_log2(uSize + uAlignment - 1);
else
index_high = index_low;
// 3. 根据策略选择搜索方式
if (policy == BEST_FIT) {
// 从最小满足条件的桶开始搜索
for (i = index_low; i < FREE_TABLE_LIMIT; i++) {
pBT = find_chunk_in_bucket(...);
if (pBT) break;
}
} else {
// 默认策略: 从稍大的桶开始
// 先找 index_high+1 及以上的桶
// 如果没找到,再向下搜索到 index_low
}
// 4. 如果找到合适的 BT,进行分割和分配
if (pBT)
return _AllocAlignSplit(pArena, pBT, uSize, uAlignment, base, phPriv);
return IMG_FALSE;
}
搜索策略图示:
请求: size=20, alignment=16
计算桶范围:
index_low = log2(20) = 4 (bucket 4: 16~31)
index_high = log2(35) = 5 (bucket 5: 32~63)
默认策略搜索顺序:
┌─────────────────────────────────┐
│ 1. 搜索 bucket[6] (64~127) │ ← 优先大块
│ 2. 搜索 bucket[7] (128~255) │
│ 3. ... 更大的桶 │
│ 4. 搜索 bucket[5] (32~63) │ ← 回退
│ 5. 搜索 bucket[4] (16~31) │
└─────────────────────────────────┘
段分割算法
static BT *_SegmentSplit(BT *pBT, RA_LENGTH_T uSize)
{
// 创建新的右邻居 BT
pNeighbour = _BuildBT(pBT->base + uSize,
pBT->uSize - uSize,
pBT->uFlags);
// 插入到段链表
_SegmentListInsertAfter(pBT, pNeighbour);
// 更新边界标志
pNeighbour->is_leftmost = 0;
pNeighbour->is_rightmost = pBT->is_rightmost;
pBT->is_rightmost = 0;
// 继承属性
pNeighbour->free_import = pBT->free_import;
pNeighbour->hPriv = pBT->hPriv;
pBT->uSize = uSize;
return pNeighbour;
}
分割示意图:
分割前:
┌───────────────────────────────────┐
│ BT (base=100, size=64) │
│ type=free │
└───────────────────────────────────┘
分割操作: _SegmentSplit(pBT, 20)
分割后:
┌─────────────────┐┌────────────────┐
│ BT1 ││ BT2 │
│ base=100 ││ base=120 │
│ size=20 ││ size=44 │
│ is_rightmost=0 ││ is_rightmost=1│
└─────────────────┘└────────────────┘
_AllocAlignSplit 处理对齐和尾部分割
static IMG_BOOL
_AllocAlignSplit(RA_ARENA *pArena,
BT *pBT,
RA_LENGTH_T uSize,
RA_LENGTH_T uAlignment,
RA_BASE_T *pBase,
RA_PERISPAN_HANDLE *phPriv)
{
// 1. 从 free list 移除
_FreeListRemove(pArena, pBT);
// 2. 计算对齐后的基址
aligned_base = PVR_ALIGN(pBT->base, uAlignment);
// 3. 如果需要,分割前面的部分
if (aligned_base > pBT->base) {
pNeighbour = _SegmentSplit(pBT, aligned_base - pBT->base);
_FreeListInsert(pArena, pBT); // 前面部分重新插入 free list
pBT = pNeighbour;
}
// 4. 如果段太大,分割后面的部分
if (pBT->uSize > uSize) {
pNeighbour = _SegmentSplit(pBT, uSize);
_FreeListInsert(pArena, pNeighbour); // 后面部分插入 free list
}
// 5. 标记为已分配并加入哈希表
pBT->type = btt_live;
HASH_Insert_Extended(pArena->pSegmentHash, &aligned_base, pBT);
*pBase = aligned_base;
return IMG_TRUE;
}
对齐和分割示意图:
初始状态:
┌─────────────────────────────────────────────┐
│ Free BT (base=100, size=100) │
└─────────────────────────────────────────────┘
请求: size=30, alignment=32
步骤1: 对齐分割
aligned_base = ALIGN(100, 32) = 128
┌──────────────┐┌──────────────────────────────┐
│ Free BT ││ Working BT │
│ base=100 ││ base=128 │
│ size=28 ││ size=72 │
└──────────────┘└──────────────────────────────┘
步骤2: 大小分割
┌──────────────┐┌─────────────┐┌──────────────┐
│ Free BT ││ Live BT ││ Free BT │
│ base=100 ││ base=128 ││ base=158 │
│ size=28 ││ size=30 ││ size=42 │
└──────────────┘└─────────────┘└──────────────┘
↑
返回此基址
释放算法流程
void RA_Free(RA_ARENA *pArena, RA_BASE_T base)
{
// 1. 从哈希表中查找并移除 BT
pBT = HASH_Remove_Extended(pArena->pSegmentHash, &base);
// 2. 更新统计
pArena->ui64FreeArenaSize += pBT->uSize;
// 3. 执行释放和合并
_FreeBT(pArena, pBT);
}
_FreeBT 详细流程
static void _FreeBT(RA_ARENA *pArena, BT *pBT)
{
// 1. 尝试与左邻居合并
pNeighbour = pBT->pPrevSegment;
if (!pBT->is_leftmost && pNeighbour->type == btt_free) {
_FreeListRemove(pArena, pNeighbour);
_SegmentListRemove(pArena, pNeighbour);
pBT->base = pNeighbour->base;
pBT->uSize += pNeighbour->uSize;
pBT->is_leftmost = pNeighbour->is_leftmost;
OSFreeMem(pNeighbour);
}
// 2. 尝试与右邻居合并
pNeighbour = pBT->pNextSegment;
if (!pBT->is_rightmost && pNeighbour->type == btt_free) {
_FreeListRemove(pArena, pNeighbour);
_SegmentListRemove(pArena, pNeighbour);
pBT->uSize += pNeighbour->uSize;
pBT->is_rightmost = pNeighbour->is_rightmost;
OSFreeMem(pNeighbour);
}
// 3. 如果形成完整的导入段,尝试释放
if (!_RemoveResourceSpan(pArena, pBT)) {
// 否则插入 free list
_FreeListInsert(pArena, pBT);
}
}
合并示意图:
释放前:
┌──────────┐┌──────────┐┌──────────┐┌──────────┐
│ Free ││ Live ││ Live ││ Free │
│ (BT1) ││ (BT2) ││ (BT3) ││ (BT4) │
└──────────┘└──────────┘└──────────┘└──────────┘
↑ 释放此BT
释放 BT2 后:
┌──────────┐┌──────────┐┌──────────┐
│ Free ││ Free ││ Free │
│ (BT1) ││ (BT2) ││ (BT4) │
└──────────┘└──────────┘└──────────┘
左合并:
┌────────────────────┐┌──────────┐
│ Free (BT1+BT2) ││ Free │
│ ││ (BT4) │
└────────────────────┘└──────────┘
释放 BT3 后:
┌────────────────────┐┌──────────┐┌──────────┐
│ Free (BT1+BT2) ││ Free ││ Free │
│ ││ (BT3) ││ (BT4) │
└────────────────────┘└──────────┘└──────────┘
右合并:
┌────────────────────┐┌─────────────────────┐
│ Free (BT1+BT2) ││ Free (BT3+BT4) │
└────────────────────┘└─────────────────────┘
最终状态(如果 BT1+BT2 和 BT3+BT4 相邻):
┌──────────────────────────────────────────┐
│ Free (BT1+BT2+BT3+BT4) │
└──────────────────────────────────────────┘
Ghost Base 机制 (稀疏分配)
Ghost Base 用于处理稀疏内存分配,减少 BT 数量。
物理布局:
┌─────────────────────────────────────────┐
│ Real Base (base=0x1000) │
│ size=4096*4 (4 pages) │
└─────────────────────────────────────────┘
逻辑表示 (Ghost Bases):
aBaseArray[0] = 0x1000 (Real)
aBaseArray[1] = 0x2000|GHOST_BIT (Ghost)
aBaseArray[2] = 0x3000|GHOST_BIT (Ghost)
aBaseArray[3] = 0x4000|GHOST_BIT (Ghost)
每个数组元素代表一个页面,但只有一个真实的 BT
Ghost Base 转换图:
// 生成 Ghost Bases
static IMG_UINT32
_GenerateGhostBases(RA_BASE_T uiRealBase,
RA_LENGTH_T uiBaseSize,
RA_LENGTH_T uiChunkSize,
RA_BASE_ARRAY_T aBaseArray)
{
IMG_UINT32 ui32Index = 0;
aBaseArray[ui32Index] = uiRealBase; // Real base
for (ui32Index = 1; uiRemaining != 0; ui32Index++) {
aBaseArray[ui32Index] = RA_BASE_SET_GHOST_BIT(uiCurrentBase);
uiCurrentBase += uiChunkSize;
uiRemaining -= uiChunkSize;
}
return ui32Index;
}
Ghost 转 Real 流程:
┌──────────────────────────────────────┐
│ 原始: [R][G][G][G] │
│ 0 1 2 3 │
└──────────────────┬───────────────────┘
│
释放 index=2 的 Ghost
│
▼
┌──────────────────────────────────────┐
│ 步骤1: 找到 Real Base (index=0) │
│ 步骤2: 分割 BT 在 index=2 │
│ 步骤3: 新 Real 插入 index=2 │
└──────────────────┬───────────────────┘
│
▼
┌──────────────────────────────────────┐
│ 结果: [R][G][R][G] │
│ 0 1 2 3 │
│ │
│ 两个独立的 BT: │
│ BT1: covers index 0,1 │
│ BT2: covers index 2,3 │
└──────────────────────────────────────┘
完整的分配/释放流程图
┌─────────────────────────────────────────────────────────────┐
│ 用户调用 RA_Alloc │
└────────────────────────┬────────────────────────────────────┘
│
▼
┌────────────────────────────────┐
│ 锁定 Arena │
│ 对齐参数到量子大小 │
└────────────┬───────────────────┘
│
▼
┌────────────────────────────────┐
│ _AttemptAllocAligned │
│ 1. Splay 查找 flags bucket │
│ 2. 计算桶索引范围 │
│ 3. 搜索合适的 BT │
└────┬───────────────────┬───────┘
│ │
成功 │ │ 失败
│ │
▼ ▼
┌─────────────┐ ┌──────────────────────┐
│返回分配结果 │ │ _AttemptImportSpan │
└─────────────┘ │ 1. 回调导入新资源 │
│ 2. 创建 span BT │
│ 3. 重试分配 │
└──────────┬───────────┘
│
▼
┌──────────────────────┐
│ 成功/失败返回 │
│ 解锁 Arena │
└──────────────────────┘
关键优化技术
Splay Tree 优化
// Splay 操作将最近访问的节点移到根
pArena->per_flags_buckets = PVRSRVSplay(uFlags, pArena->per_flags_buckets);
优势：
- 频繁访问的 flags 保持在树根附近
- 自适应平衡,无需显式平衡操作
- 时间复杂度: O(log n) 均摊
位图加速 (PVR_CTZLL)
#if defined(PVR_CTZLL)
// 使用 CTZ (Count Trailing Zeros) 快速找到第一个非空桶
i = PVR_CTZLL(
(~(((IMG_ELTS_MAPPINGS)1 << (index_high + 1)) - 1))
& pArena->per_flags_buckets->bHasEltsMapping
);
#else
// 线性搜索
for (i = index_high + 1;
i < FREE_TABLE_LIMIT && buckets[i] == NULL;
i++);
#endif
bHasEltsMapping 示意:
位图: 0000000010100110
│││││││││││││││└─ bucket[0] 非空
│││││││││││││└── bucket[1] 非空
│││││││││││└─── bucket[2] 空
│││││││││└──── bucket[5] 非空
...
查找操作: O(1) vs O(n)
策略标志
// 分配策略
RA_POLICY_ALLOC_NODE_SELECT_MASK
- RA_POLICY_ALLOC_OPTIMAL // 桶内按大小排序
- Default // 桶内不排序
// 桶选择策略
RA_POLICY_BUCKET_MASK
- RA_POLICY_BUCKET_BEST_FIT // 从小桶开始
- Default // 从大桶开始
// 其他策略
RA_POLICY_NO_SPLIT // 禁止分割
RA_POLICY_ALLOC_ALLOW_NONCONTIG // 允许非连续分配
多重分配 (Multi-Alloc)
RA_AllocMulti() 流程:
┌────────────────────────────────────────┐
│ 输入: │
│ - uRequestSize: 总大小 │
│ - uiLog2ChunkSize: 块大小(log2) │
│ - aBaseArray: 输出数组 │
└────────────┬───────────────────────────┘
│
▼
┌────────────────────────────────────────┐
│ _AttemptAllocAlignedAssured │
│ │
│ 尝试1: 寻找单个大块 │
│ - 搜索 >= uRequestSize 的 BT │
│ - 成功: 生成 Ghost Bases │
│ │
│ 尝试2: Scoop (舀取) 多个小块 │
│ - 从高桶到低桶遍历 │
│ - 累积多个 BT 直到满足总大小 │
│ - 每个 BT 生成 Ghost Bases │
└────────────┬───────────────────────────┘
│
▼
┌────────────────────────────────────────┐
│ 输出: │
│ aBaseArray 填充 Real + Ghost Bases │
│ bPhysContig 标记是否物理连续 │
└────────────────────────────────────────┘
Scoop 示意图:
请求: 100 pages, 每页 4KB
初始 Free List:
bucket[6] (64~127 pages): [BT1: 80 pages]
bucket[5] (32~63 pages): [BT2: 40 pages]
bucket[4] (16~31 pages): [BT3: 20 pages]
Scoop 过程:
1. 分配 BT1 (80 pages)
aBaseArray[0..79] = Real + 79 Ghosts
2. 分配 BT2 (20 pages, 剩余20返回 free list)
aBaseArray[80..99] = Real + 19 Ghosts
总计: 100 pages, 2个 Real Base, 98个 Ghost Base
物理上: 非连续 (bPhysContig = false)
稀疏分配 (Sparse Allocation)
稀疏分配原理
稀疏分配允许在虚拟地址空间中只映射部分物理页面，适用于大块虚拟内存但只需要部分物理内存的场景。
IMG_INTERNAL PVRSRV_ERROR
RA_AllocMultiSparse(RA_ARENA *pArena,
IMG_UINT32 uiLog2ChunkSize,
IMG_UINT8 uImportMultiplier,
RA_FLAGS_T uImportFlags,
const IMG_CHAR *pszAnnotation,
RA_BASE_ARRAY_T aBaseArray,
RA_BASE_ARRAY_SIZE_T uiBaseArraySize,
IMG_UINT32 *puiAllocIndices,
IMG_UINT32 uiAllocCount)
稀疏分配流程图
输入场景:
┌──────────────────────────────────────────────────┐
│ 虚拟数组: [][][][][][][][][] │
│ 索引: 0 1 2 3 4 5 6 7 8 │
│ │
│ 需要分配的索引: [1, 2, 3, 5, 7] │
└──────────────────────────────────────────────────┘
分配过程:
┌──────────────────────────────────────────────────┐
│ 步骤1: 索引合并优化 │
│ - 检测连续索引: [1,2,3], [5], [7] │
│ - 合并为3个分配请求 │
└───────────────────┬──────────────────────────────┘
│
▼
┌──────────────────────────────────────────────────┐
│ 步骤2: 分配连续块 │
│ 块1: indices[1-3] -> 3 chunks │
│ 调用 _RA_AllocMultiUnlocked() │
│ 生成: [R][G][G] │
│ │
│ 块2: indices[5] -> 1 chunk │
│ 调用 _RA_AllocMultiUnlocked() │
│ 生成: [R] │
│ │
│ 块3: indices[7] -> 1 chunk │
│ 调用 _RA_AllocMultiUnlocked() │
│ 生成: [R] │
└───────────────────┬──────────────────────────────┘
│
▼
┌──────────────────────────────────────────────────┐
│ 最终结果: │
│ aBaseArray[0] = INVALID_BASE_ADDR │
│ aBaseArray[1] = 0x1000 (Real) │
│ aBaseArray[2] = 0x2000|GHOST (Ghost) │
│ aBaseArray[3] = 0x3000|GHOST (Ghost) │
│ aBaseArray[4] = INVALID_BASE_ADDR │
│ aBaseArray[5] = 0x5000 (Real) │
│ aBaseArray[6] = INVALID_BASE_ADDR │
│ aBaseArray[7] = 0x7000 (Real) │
│ aBaseArray[8] = INVALID_BASE_ADDR │
└──────────────────────────────────────────────────┘
索引合并代码分析
for (i = 0; i < uiAllocCount;)
{
IMG_UINT32 j;
IMG_UINT32 uiConsolidate = 1;
// 检测连续索引
for (j = i;
j + 1 != uiAllocCount &&
puiAllocIndices[j + 1] == puiAllocIndices[j] + 1;
j++)
{
uiConsolidate++;
}
// 分配合并后的块
eError = _RA_AllocMultiUnlocked(pArena,
IMG_PAGES2BYTES64(uiConsolidate, uiLog2ChunkSize),
uiLog2ChunkSize,
uImportMultiplier,
uImportFlags,
pszAnnotation,
&aBaseArray[puiAllocIndices[i]],
uiConsolidate,
IMG_TRUE, /* Sparse alloc */
&bPhysContig);
i += uiConsolidate; // 跳过已处理的索引
}
合并优化示意:
输入索引: [0, 1, 2, 5, 6, 7, 8, 10, 15]
检测连续段:
┌────────┐ ┌──────────┐ ┌────┐ ┌────┐
│[0,1,2] │ │[5,6,7,8] │ │[10]│ │[15]│
│3个连续 │ │4个连续 │ │单个│ │单个│
└────────┘ └──────────┘ └────┘ └────┘
分配调用:
1. _RA_AllocMultiUnlocked(size=3*chunk) -> 1次分配
2. _RA_AllocMultiUnlocked(size=4*chunk) -> 1次分配
3. _RA_AllocMultiUnlocked(size=1*chunk) -> 1次分配
4. _RA_AllocMultiUnlocked(size=1*chunk) -> 1次分配
总计: 4次分配 vs 9次（如果不合并）
优化比率: 55%
稀疏释放 (Sparse Free)
IMG_INTERNAL PVRSRV_ERROR
RA_FreeMultiSparse(RA_ARENA *pArena,
RA_BASE_ARRAY_T aBaseArray,
RA_BASE_ARRAY_SIZE_T uiBaseArraySize,
IMG_UINT32 uiLog2ChunkSize,
IMG_UINT32 *puiFreeIndices,
IMG_UINT32 *puiFreeCount)
释放流程详解
释放前状态:
aBaseArray: [R][G][G][R][G][I][R][I][R][G]
索引: 0 1 2 3 4 5 6 7 8 9
释放索引: [1, 2, 4, 6]
处理过程:
┌──────────────────────────────────────────────────┐
│ 索引 1,2: 连续的 Ghost 基址 │
│ - 找到 Real base: index 0 │
│ - 调用 _ConvertAndFreeStartFromGhost() │
│ - 操作: │
│ 1. 转换 index[1] 为 Real (分割 BT) │
│ 2. 检查 index[3] (已是 Real, 无需处理) │
│ 3. 释放 index[1-2] │
└──────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────┐
│ 索引 4: 单个 Ghost 基址 │
│ - 找到 Real base: index 3 │
│ - 转换并释放 │
└──────────────────────────────────────────────────┘
┌──────────────────────────────────────────────────┐
│ 索引 6: Real 基址 │
│ - 直接释放 │
└──────────────────────────────────────────────────┘
释放后状态:
aBaseArray: [R][I][I][R'][G][I][I][I][R][G]
│ │ │
│ └─ 新的 Real │
└─ 可能合并 └─ 未改变
BT 变化:
原: BT0(0-2), BT3(3-4), BT6(6), BT8(8-9)
新: BT0(0), BT3(3), BT4(4), BT8(8-9)
Ghost 转 Real 详细过程
static PVRSRV_ERROR
_ConvertGhostBaseToReal(RA_ARENA *pArena,
RA_BASE_ARRAY_T aBaseArray,
RA_BASE_T uiRealBase,
IMG_UINT32 ui32RealBaseArrayIndex,
IMG_UINT32 ui32GhostBaseArrayIndex,
RA_LENGTH_T uiChunkSize)
{
// 1. 从哈希表获取原 Real BT
pOrigRealBT = HASH_Retrieve_Extended(pArena->pSegmentHash, &uiRealBase);
// 2. 计算分割位置并分割
IMG_UINT32 offset = ui32GhostBaseArrayIndex - ui32RealBaseArrayIndex;
pNewRealBT = _SegmentSplit(pOrigRealBT, uiChunkSize * offset);
// 3. 将新 BT 加入哈希表
HASH_Insert_Extended(pArena->pSegmentHash, &pNewRealBT->base, pNewRealBT);
// 4. 更新数组
aBaseArray[ui32GhostBaseArrayIndex] = pNewRealBT->base;
return PVRSRV_OK;
}
转换示意图:
初始状态:
Array: [R][G][G][G]
Index: 0 1 2 3
BT: └─BT0────┘
base=0x1000
size=16K
转换 index[2] 为 Real:
┌──────────────────────────────────────┐
│ 1. 查找 Real base: index[0] │
│ 2. 计算偏移: offset = 2 - 0 = 2 │
│ 3. 分割位置: 0x1000 + 2*4K = 0x3000 │
└──────────────────────────────────────┘
分割后:
Array: [R][G][R'][G]
Index: 0 1 2 3
BT: └BT0┘└BT2─┘
0x1000 0x3000
8K 8K
哈希表更新:
Before: {0x1000 -> BT0}
After: {0x1000 -> BT0, 0x3000 -> BT2}
三种释放场景
static PVRSRV_ERROR
_ConvertAndFreeBaseArraySlice(RA_ARENA *pArena,
RA_BASE_ARRAY_T aBaseArray,
RA_BASE_ARRAY_SIZE_T uiBaseArraySize,
RA_LENGTH_T uiChunkSize,
IMG_UINT32 uiFreeStartIndex,
IMG_UINT32 uiFreeCount,
RA_CONVERT_AND_FREE_BEHAVIOUR eBehaviour)
场景1: 完整 Real Base 释放
Array: [R][G][G][G] 全部释放
Result: [I][I][I][I]
操作: 直接调用 _FreeSingleBaseArray()
场景2: 部分从 Real 开始释放
Array: [R][G][G][G][G] 释放 index[0-2]
Before: └────BT0──────┘
After: [I][I][I][R'][G]
└─BT1─┘
步骤:
1. 转换 index[3] 为 Real (分割 BT0)
2. 释放 BT0 (index[0-2])
3. 保留 BT1 (index[3-4])
场景3: Ghost 段释放
Array: [R][G][G][G][G] 释放 index[1-3]
Before: └────BT0──────┘
After: [R'][I][I][I][R'']
└BT0┘ └BT1┘
步骤:
1. 转换 index[1] 为 Real (分割原 BT)
2. 转换 index[4] 为 Real (再次分割)
3. 释放中间的 BT (index[1-3])
4. 保留两端
内存交换 (Swap) 机制
RA_SwapSparseMem 流程
IMG_INTERNAL PVRSRV_ERROR
RA_SwapSparseMem(RA_ARENA *pArena,
RA_BASE_ARRAY_T aBaseArray,
RA_BASE_ARRAY_SIZE_T uiBaseArraySize,
IMG_UINT32 uiLog2ChunkSize,
IMG_UINT32 *puiXIndices,
IMG_UINT32 *puiYIndices,
IMG_UINT32 uiSwapCount)
交换算法详解
目标: 交换 X 和 Y 索引位置的内容
输入示例:
Array: [R0][G][G][R1][G][G][R2][G]
Index: 0 1 2 3 4 5 6 7
X索引: [1, 2, 3]
Y索引: [5, 6, 7]
算法流程:
┌──────────────────────────────────────────────────┐
│ 步骤1: 索引合并 │
│ X: [1,2,3] -> 连续3个 │
│ Y: [5,6,7] -> 连续3个 │
│ 取最小: min(3,3) = 3 │
└───────────────────┬──────────────────────────────┘
│
▼
┌──────────────────────────────────────────────────┐
│ 步骤2: 修剪边界 (Trim Block) │
│ X块: [1-3] │
│ - 检查 index[1]: 如果是 Ghost, 转为 Real │
│ - 检查 index[4]: 如果是 Ghost, 转为 Real │
│ Y块: [5-7] │
│ - 检查 index[5]: 如果是 Ghost, 转为 Real │
│ - 检查 index[8]: 如果存在且是Ghost,转为Real │
└───────────────────┬──────────────────────────────┘
│
▼
┌──────────────────────────────────────────────────┐
│ 步骤3: 执行交换 │
│ SWAP(aBaseArray[1], aBaseArray[5]) │
│ SWAP(aBaseArray[2], aBaseArray[6]) │
│ SWAP(aBaseArray[3], aBaseArray[7]) │
└──────────────────────────────────────────────────┘
修剪边界函数
static PVRSRV_ERROR
_TrimBlockMakeReal(RA_ARENA *pArena,
RA_BASE_ARRAY_T aBaseArray,
RA_BASE_ARRAY_SIZE_T uiBaseArraySize,
IMG_UINT32 uiLog2ChunkSize,
IMG_UINT32 uiStartIndex,
IMG_UINT32 uiEndIndex)
{
// 1. 确保起始索引是 Real
if (RA_BASE_IS_GHOST(aBaseArray[uiStartIndex])) {
_FindRealBaseFromGhost(...);
_ConvertGhostBaseToReal(...);
}
// 2. 确保结束索引+1是 Real (如果不是数组末尾)
if (uiEndIndex + 1 != uiBaseArraySize &&
RA_BASE_IS_GHOST(aBaseArray[uiEndIndex + 1])) {
_FindRealBaseFromGhost(...);
_ConvertGhostBaseToReal(...);
}
return PVRSRV_OK;
}
修剪示意图:
交换前准备:
Array: [R0][G][G][G][R1][G][G][G]
Index: 0 1 2 3 4 5 6 7
交换范围: X=[1-3], Y=[5-7]
修剪 X 块 [1-3]:
┌──────────────────────────────────────┐
│ 起始: index[1] 是 Ghost │
│ 找到 Real: index[0] │
│ 分割: 创建 index[1] 为 Real │
│ 结束: index[4] 是 Real, 无需处理 │
└──────────────────────────────────────┘
修剪后: [R0][R1'][G][G][R1][G][G][G]
└─────X块────┘
修剪 Y 块 [5-7]:
┌──────────────────────────────────────┐
│ 起始: index[5] 是 Ghost │
│ 找到 Real: index[4] │
│ 分割: 创建 index[5] 为 Real │
│ 结束: index[8] 不存在, 无需处理 │
└──────────────────────────────────────┘
修剪后: [R0][R1'][G][G][R1][R2'][G][G]
└─────Y块────┘
现在可以安全交换 X 和 Y 块
完整交换示例
初始状态:
Array: [R0][G][G][R1][G][G]
Index: 0 1 2 3 4 5
值: A0 A1 A2 B0 B1 B2
交换操作: X=[1,2], Y=[4,5]
步骤1: 修剪
Array: [R0][R'][G][R1][R''][G]
A0 A1 A2 B0 B1 B2
步骤2: 交换
SWAP([1],[4]): A1 <-> B1
SWAP([2],[5]): A2 <-> B2
最终状态:
Array: [R0][R'][G][R1][R''][G]
A0 B1 B2 B0 A1 A2
BT 结构:
- BT(A0): index[0]
- BT(B1-B2): index[1-2]
- BT(B0): index[3]
- BT(A1-A2): index[4-5]
Import/Export 机制
资源导入流程
导入时机: 当 Arena 资源不足时
单次导入 (SINGLE):
┌─────────────────────────────────────────┐
│ pImportAllocSingle(handle, size, flags) │
└────────────────┬────────────────────────┘
│
▼
┌────────────────┐
│ RA_IMPORT │
│ - base │
│ - uSize │
│ - hPriv │
└────────┬───────┘
│
▼
┌────────────────┐
│ _InsertResource│
│ Span(...) │
└────────┬───────┘
│
▼
┌────────────────┐
│ 创建 BT │
│ 标记 free_ │
│ import=1 │
└────────────────┘
多次导入 (MULTI):
eError = pArena->pImportAllocMulti(
pArena->pImportHandle,
uRequestSize,
uImportFlags,
uAlignment,
pszAnnotation,
puiImportCount, // [in/out] 导入数量
(RA_IMPORT**)ppsImports // [out] 导入数组
);
// 可能返回多个不连续的内存段
// 例如: 请求 1MB, 可能返回:
// - Import[0]: 512KB @ 0x1000
// - Import[1]: 256KB @ 0x5000
// - Import[2]: 256KB @ 0x9000
导入倍数优化
// uImportMultiplier 参数允许预分配
RA_Alloc(..., uImportMultiplier=2, ...)
计算导入大小:
uRequestSize *= uImportMultiplier;
uRequestSize = PVR_ALIGN(uRequestSize, pArena->uQuantum);
// 如果请求 64KB, multiplier=2
// 实际导入: 128KB
// 额外的 64KB 保留在 free list 中供未来使用
导入倍数示意:
场景: 频繁小额分配
策略1: multiplier = 1 (按需导入)
┌────────┐ ┌────────┐ ┌────────┐
│ 导入1 │ │ 导入2 │ │ 导入3 │
│ 4KB │ │ 4KB │ │ 4KB │
└────────┘ └────────┘ └────────┘
3次导入调用, 3次系统调用
策略2: multiplier = 4 (预分配)
┌──────────────────────────────┐
│ 导入1 │
│ 16KB │
├──────┬──────┬──────┬──────────┤
│ 用1 │ 用2 │ 用3 │ Free │
│ 4KB │ 4KB │ 4KB │ 4KB │
└──────┴──────┴──────┴──────────┘
1次导入调用, 1次系统调用
优势: 减少系统调用开销, 改善局部性
资源释放与回收
static INLINE IMG_BOOL
_RemoveResourceSpan(RA_ARENA *pArena, BT *pBT)
{
// 仅当满足以下所有条件时才释放导入:
// 1. free_import = 1 (标记为可释放)
// 2. is_leftmost = 1 (整个导入段的左端)
// 3. is_rightmost = 1 (整个导入段的右端)
if (pBT->free_import &&
pBT->is_leftmost &&
pBT->is_rightmost)
{
// 从段列表移除
_SegmentListRemove(pArena, pBT);
// 更新统计
pArena->ui64TotalArenaSize -= pBT->uSize;
pArena->ui64FreeArenaSize -= pBT->uSize;
// 调用释放回调
pArena->pImportFree(pArena->pImportHandle,
pBT->base,
pBT->hPriv);
// 释放 BT
OSFreeMem(pBT);
return IMG_TRUE;
}
return IMG_FALSE;
}
释放条件示意:
导入段: [0x1000, 16KB]
情况1: 部分使用
┌────────┬────────┬────────┐
│ Live │ Free │ Free │
│ 4KB │ 4KB │ 8KB │
└────────┴────────┴────────┘
is_leftmost=1 is_rightmost=1
但有 Live 段 -> 不释放
情况2: 完全空闲但已分割
┌────────┬──────────────────┐
│ Free │ Free │
│ 4KB │ 12KB │
└────────┴──────────────────┘
左BT: is_rightmost=0 -> 不释放
右BT: is_leftmost=0 -> 不释放
情况3: 完全空闲且未分割
┌──────────────────────────┐
│ Free │
│ 16KB │
└──────────────────────────┘
is_leftmost=1 && is_rightmost=1
free_import=1 -> 释放!
迭代器 (Iterator) 机制
迭代器结构
struct _RA_ARENA_ITERATOR_ {
RA_ARENA *pArena; // 目标 Arena
BT *pCurrent; // 当前 BT
IMG_BOOL bIncludeFreeSegments; // 是否包含空闲段
};
迭代模式
模式1: 仅 Live 段
pIter = RA_IteratorAcquire(pArena, IMG_FALSE);
while (RA_IteratorNext(pIter, &sData)) {
// 只访问已分配的段
// sData.uiAddr, sData.uiSize
}
RA_IteratorRelease(pIter);
模式2: 所有段 (含 Free)
pIter = RA_IteratorAcquire(pArena, IMG_TRUE);
while (RA_IteratorNext(pIter, &sData)) {
if (sData.bFree) {
// 空闲段
} else {
// 已分配段
}
}
模式3: 按 Span 迭代
pIter = RA_IteratorAcquire(pArena, IMG_TRUE);
while (RA_IteratorNextSpan(pIter, &sData)) {
// 每次返回一个完整的导入 span
// 包含该 span 内的所有段 (Live + Free)
}
段合并逻辑
IMG_BOOL RA_IteratorNext(RA_ARENA_ITERATOR *pIter, RA_ITERATOR_DATA *pData)
{
pData->uiAddr = pIter->pCurrent->base;
pData->uiSize = pIter->pCurrent->uSize;
pData->bFree = pIter->pCurrent->type == btt_free;
// 合并相同类型的连续段
while ((pNext = pNext->pNextSegment) != NULL &&
pNext->type == pNext->pPrevSegment->type &&
pNext->type == btt_live && // 只合并 Live 段
pNext->base == pData->uiAddr + pData->uiSize)
{
pData->uiSize += pNext->uSize;
}
// 跳到下一个 Live 段 (如果 !bIncludeFreeSegments)
...
}
合并示意:
Segment List:
┌─────┬─────┬─────┬─────┬─────┐
│Live │Live │Free │Live │Live │
│ 4K │ 4K │ 8K │ 4K │ 4K │
└─────┴─────┴─────┴─────┴─────┘
迭代结果 (bIncludeFreeSegments=False):
1. {addr=..., size=8K, free=false} // 合并前两个
2. {addr=..., size=8K, free=false} // 合并后两个
迭代结果 (bIncludeFreeSegments=True):
1. {addr=..., size=8K, free=false}
2. {addr=..., size=8K, free=true}
3. {addr=..., size=8K, free=false}
Block Dump 可视化
RA_BlockDump 功能
生成 Arena 内存布局的可视化图，用于调试和分析。
IMG_INTERNAL PVRSRV_ERROR
RA_BlockDump(RA_ARENA *pArena,
void (*pfnLogDump)(void*, IMG_CHAR*, ...),
void *pPrivData)
可视化输出示例
~~~ 'GPU_VM' Resource Arena Block Dump
Block Size: 4096B
Span Memory Usage: 268435456B
Free Span Memory: 134217728B
Largest Free Region Size: 67108864B
Percent Fragmented 66%
===============================================================================
| 0x00000000 | ################################################################
| 0x00010000 | ################................................................
| 0x00020000 | ................................................................
| 0x00030000 | ................................################################
....
| 0x0FFF0000 | ################################################................
图例:
# = 已分配
. = 空闲
实现原理
数据结构:
papRegionArray[region_idx][chunk_idx]
│
├─ region: 代表一段连续地址范围
│ - 每个 region = uiRegionSize = 128 blocks (默认)
│
└─ chunk: 每个 chunk 用32位整数表示
- chunk_idx 范围: 0 ~ uiChunkCount (通常4个)
- 每个 chunk 代表 32 个 blocks
- 每个 bit 代表一个 block 的分配状态
可视化映射:
┌─────────────────────────────────────────────────┐
│ Region 0 │
├─────────────────────────────────────────────────┤
│ Chunk[0] Chunk[1] Chunk[2] Chunk[3] │
│ 32bits 32bits 32bits 32bits │
│ ──────── ──────── ──────── ──────── │
│ 0-31 32-63 64-95 96-127 │
└─────────────────────────────────────────────────┘
输出为两行 64 字符:
Line 1: Chunk[0] 和 Chunk[1] 的可视化 (64字符)
Line 2: Chunk[2] 和 Chunk[3] 的可视化 (64字符)
代码详解
// 1. 确定需要多少 regions
uiRecognisedQuantum = pArena->uQuantum > 0 ? pArena->uQuantum : 4096;
// 找到最后一个分配的地址
while (RA_IteratorNext(pIter, &sIterData)) {
if (!sIterData.bFree && sIterData.uiAddr >= uiLastBase) {
uiLastBase = sIterData.uiAddr;
uiLastSize = sIterData.uiSize;
}
}
// 计算 region 数量
uiRegionCount = (uiLastBase + uiLastSize) / uiRecognisedQuantum / uiRegionSize;
// 2. 填充位图
while (RA_IteratorNext(pIter, &sIterData)) {
if (sIterData.bFree) {
uiLargestFreeSegmentSize = max(uiLargestFreeSegmentSize, sIterData.uiSize);
continue; // 跳过空闲段
}
// 计算分配在哪个 region 和 chunk
uiDataDivRecQuant = sIterData.uiAddr / uiRecognisedQuantum;
uiAddrRegionIdx = uiDataDivRecQuant / uiRegionSize;
uiAddrRegionOffset = uiDataDivRecQuant % uiRegionSize;
uiAddrChunkIdx = uiAddrRegionOffset / uiChunkSize;
uiAddrChunkOffset = uiAddrRegionOffset % uiChunkSize;
// 计算分配占用多少个 blocks
uiQuantisedSize = sIterData.uiSize / uiRecognisedQuantum;
if (sIterData.uiSize % uiRecognisedQuantum != 0) {
uiQuantisedSize++;
}
// 在位图中标记
// ... (设置对应的 bits)
}
// 3. 打印可视化
for (i = 0; i < uiRegionCount; i++) {
if (papRegionArray[i] != NULL) {
for (j = 0; j < uiChunkCount; j+=2) {
// 将两个 chunks (64 bits) 转换为 64 个字符
for (k = 1 << 31; k != 0; k >>= 1) {
pszLine[uiBit] = papRegionArray[i][j] & k ? '#' : '.';
pszLine[32 + uiBit] = papRegionArray[i][j+1] & k ? '#' : '.';
uiBit++;
}
// 计算并打印地址
IMG_UINT64 uiLineAddress =
(i * uiRegionSize + (j >> 1) * uiLineWidth) * uiRecognisedQuantum;
pfnLogDump(pPrivData, "| 0x%08llx | %s", uiLineAddress, pszLine);
}
}
}
位图填充详细示例
示例分配:
- 地址: 0x1000
- 大小: 0x5000 (20KB)
- Block大小: 4KB
- 量化大小: 5 blocks
计算过程:
uiDataDivRecQuant = 0x1000 / 0x1000 = 1
uiAddrRegionIdx = 1 / 128 = 0 (region 0)
uiAddrRegionOffset = 1 % 128 = 1
uiAddrChunkIdx = 1 / 32 = 0 (chunk 0)
uiAddrChunkOffset = 1 % 32 = 1
需要设置的 bits:
Chunk[0], bits [1-5] (5 个连续 bits)
位图操作:
初始: 00000000000000000000000000000000 (32 bits)
│││││││││││││││││││││││││││││││└─ bit 0
设置 bits 1-5:
结果: 00000000000000000000000000111110
│││││└─ bit 1
││││└── bit 2
│││└─── bit 3
││└──── bit 4
│└───── bit 5
转换为字符:
.####.............................. (32 字符)
碎片化计算
// 碎片化百分比计算
if (pArena->ui64FreeArenaSize && uiLargestFreeSegmentSize) {
uiFragPercentage =
100 * pArena->ui64FreeArenaSize /
(pArena->ui64FreeArenaSize + uiLargestFreeSegmentSize);
}
碎片化示意:
场景1: 低碎片化
┌──────────────────────────────────────────────┐
│ Live │ Live │ Free (Large) │
│ 10MB │ 10MB │ 180MB │
└──────────────────────────────────────────────┘
总空闲: 180MB
最大连续空闲: 180MB
碎片化: 100 * 180 / (180 + 180) = 50%
场景2: 高碎片化
┌──────────────────────────────────────────────┐
│ Live │ Free │ Live │ Free │ ... │ Free │
│ 5MB │ 5MB │ 5MB │ 5MB │ ... │ 5MB │
└──────────────────────────────────────────────┘
总空闲: 90MB (18个5MB块)
最大连续空闲: 5MB
碎片化: 100 * 90 / (90 + 5) = 94%
策略标志详解
RA_POLICY_T 标志位
// 分配节点选择策略
RA_POLICY_ALLOC_NODE_SELECT_MASK = 0x00000001
RA_POLICY_ALLOC_OPTIMAL = 0x00000001 // 桶内按大小排序
// 桶选择策略
RA_POLICY_BUCKET_MASK = 0x00000002
RA_POLICY_BUCKET_BEST_FIT = 0x00000002 // 最佳适配
// 分割策略
RA_POLICY_NO_SPLIT_MASK = 0x00000004
RA_POLICY_NO_SPLIT = 0x00000004 // 禁止分割
// 非连续分配策略
RA_POLICY_ALLOC_ALLOW_NONCONTIG_MASK = 0x00000008
策略对比
OPTIMAL vs 默认 (桶内排序)
默认策略 (无排序):
Bucket[5] (32~63 pages):
-> BT1(40 pages) -> BT2(35 pages) -> BT3(60 pages) -> NULL
插入顺序: 先进先出 (FIFO)
查找: 返回第一个满足条件的
OPTIMAL 策略 (按大小排序):
Bucket[5] (32~63 pages):
-> BT2(35 pages) -> BT1(40 pages) -> BT3(60 pages) -> NULL
↑小 大↑
插入: 按大小顺序插入
查找: 返回最小满足条件的
优势: 减少碎片化，保留大块供后续大分配使用
BEST_FIT vs 默认 (桶选择)
请求: 20 pages
默认策略:
1. 查找 bucket[5] 及以上 (32+ pages)
2. 如果没找到，回退到 bucket[4] (16~31 pages)
优势: 快速，优先使用大块
BEST_FIT 策略:
1. 查找 bucket[4] (16~31 pages)
2. 如果没找到，向上查找更大的桶
优势: 节省内存，减少浪费
示例:
可用: bucket[4]: BT(25 pages)
bucket[6]: BT(80 pages)
默认: 选择 80 pages，浪费 60 pages
BEST_FIT: 选择 25 pages，浪费 5 pages
NO_SPLIT 策略
if ((pArena->ui32PolicyFlags & RA_POLICY_NO_SPLIT_MASK) == RA_POLICY_NO_SPLIT) {
goto nosplit;
}
// 跳过所有分割逻辑
nosplit:
pBT->type = btt_live;
HASH_Insert_Extended(pArena->pSegmentHash, &aligned_base, pBT);
*pBase = aligned_base;
return IMG_TRUE;
使用场景:
场景: 硬件要求整块分配
请求: 20 pages, 找到 BT(64 pages)
默认策略:
┌────────┬──────────────────────────┐
│ 20 pg │ 44 pg (返回 Free) │
└────────┴──────────────────────────┘
返回: 20 pages
NO_SPLIT 策略:
┌────────────────────────────────────┐
│ 64 pg (全部分配) │
└────────────────────────────────────┘
返回: 64 pages
优势: 避免分割开销，硬件可能有整块要求
劣势: 浪费内存
线程安全与锁机制
锁类 (Lock Class)
struct _RA_ARENA_ {
POS_LOCK hLock; // Arena 锁
IMG_UINT32 ui32LockClass; // 锁类标识
};
// 获取锁时使用锁类
OSLockAcquireNested(pArena->hLock, pArena->ui32LockClass);
锁类层次:
RA_LOCKCLASS_0: 顶层 Arena，不依赖其他 Arena
RA_LOCKCLASS_1: 依赖 LOCKCLASS_0 的 Arena
RA_LOCKCLASS_2: 依赖 LOCKCLASS_1 的 Arena
嵌套规则:
允许: LOCKCLASS_0 -> LOCKCLASS_1 -> LOCKCLASS_2
禁止: LOCKCLASS_1 -> LOCKCLASS_0 (死锁风险)
示例层次:
┌──────────────────────┐
│ Physical Memory Arena│ <- LOCKCLASS_0
│ (不依赖其他Arena) │
└──────────┬───────────┘
│
▼
┌──────────────────────┐
│ GPU VM Arena │ <- LOCKCLASS_1
│ (导入物理内存) │
└──────────┬───────────┘
│
▼
┌──────────────────────┐
│ Device Memory Arena │ <- LOCKCLASS_2
│ (导入GPU VM) │
└──────────────────────┘
临界区保护
// 所有公共 API 都遵循此模式
IMG_INTERNAL PVRSRV_ERROR RA_Alloc(...)
{
OSLockAcquireNested(pArena->hLock, pArena->ui32LockClass);
// 临界区操作
// - 修改 Segment List
// - 修改 Free Table
// - 修改 Hash Table
OSLockRelease(pArena->hLock);
return eError;
}
保护的数据结构:
Arena 锁保护:
├─ pHeadSegment (段链表头)
├─ per_flags_buckets (Splay Tree)
├─ pSegmentHash (哈希表)
├─ ui64TotalArenaSize (统计)
└─ ui64FreeArenaSize (统计)
每个 BT 的链表指针:
├─ pNextSegment / pPrevSegment
├─ next_free / prev_free
└─ 由 Arena 锁隐式保护
回调函数与锁
// 导入回调可能会获取外部锁
eError = pArena->pImportAllocSingle(
pArena->pImportHandle,
uRequestSize,
uImportFlags,
uAlignment,
pszAnnotation,
psImport
);
// 注意:
// 1. 回调内部可能锁定其他 Arena (必须遵循锁类层次)
// 2. 当前 Arena 锁仍然持有
// 3. 回调不应尝试递归锁定当前 Arena
死锁预防示例:
正确的嵌套:
Thread 1:
Lock(PhysArena, CLASS_0)
-> ImportCallback()
-> Lock(VMArena, CLASS_1) ✓ 允许
错误的嵌套:
Thread 1:
Lock(VMArena, CLASS_1)
-> ImportCallback()
-> Lock(PhysArena, CLASS_0) ✗ 违反层次
Thread 2:
Lock(PhysArena, CLASS_0)
-> ...
-> Lock(VMArena, CLASS_1)
结果: 潜在死锁
性能分析与优化建议
时间复杂度分析
操作 最坏情况 平均情况 说明
─────────────────────────────────────────────────
Alloc (查找) O(log n) O(log n) Splay Tree + 桶搜索
Alloc (分割) O(1) O(1) 常数时间创建 BT
Free (查找) O(1) O(1) 哈希表查找
Free (合并) O(1) O(1) 最多检查2个邻居
Insert Hash O(1) O(1) 哈希表插入
Splay O(n) O(log n) 均摊 O(log n)
其中 n = 不同 flags 的数量（通常很小）
空间复杂度
每个 Arena:
- 固定开销: sizeof(RA_ARENA) ≈ 128 bytes
- Splay Tree: n * sizeof(PSPLAY_TREE) ≈ n * 1KB
(n = 不同 flags 数量)
- Hash Table: m * sizeof(hash_entry)
(m = 已分配段数量)
每个 BT:
- sizeof(BT) ≈ 80 bytes
示例计算:
1000 个分配，10 种不同 flags:
- Arena: 128 bytes
- Splay: 10 * 1024 = 10KB
- Hash: 1000 * 32 = 32KB
- BTs: 约 2000 个 (包括 free) * 80 = 160KB
总计: ≈ 202KB 元数据开销
优化建议
导入倍数优化
// 频繁小分配场景
RA_Alloc(pArena, 4KB,
4, // multiplier=4, 预分配16KB
...);
优势:
- 减少导入次数
- 改善内存局部性
- 减少系统调用开销
代价:
- 可能浪费内存
- 增加初始分配延迟
策略选择
// 场景1: 内存充足，追求速度
RA_Create(...,
0); // 默认策略
// 场景2: 内存紧张，追求利用率
RA_Create(...,
RA_POLICY_BUCKET_BEST_FIT |
RA_POLICY_ALLOC_OPTIMAL);
量子大小选择
// 小量子: 精细管理，但开销大
RA_Create(..., 0); // 4KB 量子
// 大量子: 粗粒度管理，减少 BT 数量
RA_Create(..., 4); // 64KB 量子
权衡:
量子大小 | BT数量 | 碎片化 | 管理开销
─────────────────────────────────────
4KB | 多 | 低 | 高
64KB | 少 | 高 | 低
稀疏分配优化
// 避免: 逐个分配
for (i = 0; i < 1000; i++) {
RA_Alloc(pArena, PAGE_SIZE, ...);
}
// 优化: 批量稀疏分配
IMG_UINT32 indices[1000];
for (i = 0; i < 1000; i++) indices[i] = i;
RA_AllocMultiSparse(pArena,
LOG2_PAGE_SIZE,
...,
aBaseArray,
1000,
indices,
1000);
优势:
- 单次锁获取
- 索引合并优化
- 减少 BT 数量 (Ghost Base)
常见性能陷阱
陷阱1: 频繁小额分配
问题:
for (i = 0; i < 10000; i++) {
RA_Alloc(pArena, 4KB, 1, ...); // multiplier=1
}
影响:
- 10000 次锁操作
- 10000 次哈希插入
- 可能触发 10000 次导入
解决:
- 使用 multiplier > 1
- 使用 AllocMulti
- 使用内存池
陷阱2: 碎片化累积
场景:
重复: Alloc(8KB) -> Free(4KB) -> Alloc(4KB)
结果:
┌────┬────┬────┬────┬────┬────┐
│4KB │Free│4KB │Free│4KB │Free│
└────┴────┴────┴────┴────┴────┘
问题: 无法分配 > 4KB 的连续块
解决:
- 定期压缩 (如果支持)
- 使用更大的量子
- 分离不同大小的 Arena
陷阱3: 锁竞争
多线程场景:
Thread 1: RA_Alloc(ArenaA)
Thread 2: RA_Alloc(ArenaA) // 等待
Thread 3: RA_Alloc(ArenaA) // 等待
解决:
- 使用多个 Arena 分片
- 线程本地缓存
- 批量操作减少锁持有时间
使用示例
基本用法
// 1. 创建 Arena
RA_ARENA *pArena = RA_Create(
"MyArena", // 名称
0, // log2 量子 (4KB)
RA_LOCKCLASS_0, // 锁类
MyImportAlloc, // 导入回调
MyImportFree, // 释放回调
pvImportHandle, // 导入句柄
0 // 默认策略
);
// 2. 分配资源
RA_BASE_T base;
RA_LENGTH_T actualSize;
PVRSRV_ERROR eError;
eError = RA_Alloc(
pArena,
SIZE_64KB, // 请求大小
2, // 导入倍数
0, // 标志
SIZE_4KB, // 对齐
"TestAlloc", // 注释
&base, // 输出基址
&actualSize, // 实际大小
NULL // 私有数据
);
// 3. 使用资源
if (eError == PVRSRV_OK) {
// 使用 [base, base+actualSize)
}
// 4. 释放资源
RA_Free(pArena, base);
// 5. 销毁 Arena
RA_Delete(pArena);
稀疏分配示例
// 分配虚拟地址空间但只映射部分物理页
#define VIRT_SIZE_PAGES 1024
#define PHYS_SIZE_PAGES 256
RA_BASE_ARRAY_T aBaseArray[VIRT_SIZE_PAGES];
IMG_UINT32 aiMapIndices[PHYS_SIZE_PAGES];
IMG_BOOL bPhysContig;
// 1. 分配虚拟地址范围
eError = RA_AllocMulti(
pVMArena,
VIRT_SIZE_PAGES * PAGE_SIZE,
LOG2_PAGE_SIZE,
1, // multiplier
0, // flags
"SparseVM",
aBaseArray,
VIRT_SIZE_PAGES,
&bPhysContig
);
// 2. 选择要映射的页面
for (i = 0; i < PHYS_SIZE_PAGES; i++) {
aiMapIndices[i] = rand() % VIRT_SIZE_PAGES;
}
// 3. 分配物理内存到选定页面
eError = RA_AllocMultiSparse(
pPhysArena,
LOG2_PAGE_SIZE,
1,
0,
"SparsePhys",
aBaseArray, // 同一数组
VIRT_SIZE_PAGES,
aiMapIndices,
&PHYS_SIZE_PAGES
);
// 现在 aBaseArray 包含:
// - Real bases 在 aiMapIndices 指定的位置
// - Ghost bases 用于虚拟连续性
// - INVALID_BASE_ADDR 在未映射位置
按需映射示例
// 初始: 全虚拟分配，无物理映射
RA_BASE_ARRAY_T aBaseArray[NUM_PAGES];
eError = RA_AllocMulti(pVMArena, TOTAL_SIZE, ...);
// 所有页面初始为 INVALID_BASE_ADDR 或 Ghost
// 页面错误处理: 按需分配物理页
void HandlePageFault(IMG_UINT32 uiPageIndex)
{
IMG_UINT32 aiIndices[1] = {uiPageIndex};
IMG_UINT32 uiCount = 1;
// 分配一个物理页到指定索引
RA_AllocMultiSparse(
pPhysArena,
LOG2_PAGE_SIZE,
1,
0,
"OnDemand",
aBaseArray,
NUM_PAGES,
aiIndices,
&uiCount
);
// 建立页表映射
MapPage(aBaseArray[uiPageIndex], uiPageIndex);
}
// 释放不常用页面
void EvictPage(IMG_UINT32 uiPageIndex)
{
IMG_UINT32 aiIndices[1] = {uiPageIndex};
IMG_UINT32 uiCount = 1;
// 取消映射
UnmapPage(uiPageIndex);
// 释放物理内存
RA_FreeMultiSparse(
pPhysArena,
aBaseArray,
NUM_PAGES,
LOG2_PAGE_SIZE,
aiIndices,
&uiCount
);
aBaseArray[uiPageIndex] = INVALID_BASE_ADDR;
}
总结
核心设计思想
1. 分层管理
┌─────────────┐
│ Splay Tree │ <- flags 分类
└──────┬──────┘
│
┌──────▼──────┐
│ Buckets │ <- 大小分类 (log2)
└──────┬──────┘
│
┌──────▼──────┐
│ BT Chains │ <- 具体段
└─────────────┘
2. 延迟合并
- 只在必要时合并相邻空闲段
- 避免过度合并/分割
3. Ghost Base
- 减少元数据
- 支持稀疏分配
- 按需转换为 Real
4. 策略可配置
- 适应不同使用场景
- 平衡速度与利用率
适用场景
✓ GPU 虚拟地址空间管理
✓ 物理内存分配
✓ 设备内存管理
✓ 大范围稀疏资源分配
✓ 需要对齐的资源分配
✗ 频繁极小分配 (< 4KB)
✗ 实时系统 (锁开销)
✗ 严格 O(1) 要求的场景
关键优势
- 通用性: 可管理任意整数资源
- 可扩展: 支持多种导入方式
- 高效: 对数时间复杂度，位图加速
- 灵活: 丰富的策略选项
- 稀疏支持: Ghost Base 机制
- 线程安全: 完整的锁保护
- 可调试: Block Dump 可视化
架构图总览
┌──────────────────────────┐
│ User API │
│ Alloc / Free / Iterator │
└────────────┬─────────────┘
│
┌────────────▼─────────────┐
│ RA_ARENA │
│ - Lock │
│ - Policy │
│ - Statistics │
└────────────┬─────────────┘
│
┌───────────────┼───────────────┐
│ │ │
┌────────▼────────┐ ┌───▼────┐ ┌───────▼────────┐
│ Segment List │ │ Splay │ │ Segment Hash │
│ (Address Order)│ │ Tree │ │ (Live Segs) │
└────────┬────────┘ └───┬────┘ └────────────────┘
│ │
│ ┌────────▼────────┐
│ │ Buckets │
│ │ (Size Classes) │
│ └────────┬────────┘
│ │
└──────┬───────┘
│
┌───────▼────────┐
│ Boundary Tags │
│ (BT) │
│ - base │
│ - size │
│ - type │
│ - flags │
└────────────────┘
这个 Resource Allocator 是一个精心设计的内存管理系统，通过多层索引、智能分割/合并、Ghost Base 等技术，在通用性、性能和内存效率之间取得了良好的平衡。
