指针扫描完整实现计划 v3（两轮 Review 后终版）

struct ce_ptr_entry {
    uint64_t source;  // 指针存放地址
    uint64_t target;  // 指针的值（已 untag）
};
 
struct ce_ptrscan_collect_req {
    int           pid;
    uint32_t      flags;          // PTRSCAN_ALIGNED(1) | PTRSCAN_WRITABLE(2)
    uint32_t      max_results;    // 0 = 5M default
    unsigned long result_buf;     // 用户态 buffer: ce_ptr_entry[]
    uint32_t      result_count;   // out: 实际数量
};
 
#define PTRSCAN_ALIGNED_ONLY   (1 << 0)
#define PTRSCAN_WRITABLE_ONLY  (1 << 1)
#define SHADOW_CE_PTRSCAN_COLLECT _IOWR(CE_IOC_MAGIC, 20, struct ce_ptrscan_collect_req)

static int do_ptrscan_collect(struct ce_ptrscan_collect_req *req)
{
    struct task_struct *task;
    struct mm_struct *mm;
    struct vm_area_struct *vma;
    uint32_t max_res = req->max_results ? min(req->max_results, 5000000u) : 5000000;
    uint32_t found = 0;
    int ret = 0;
 
    // 1. vmalloc 结果 buffer（最大 80MB）
    struct ce_ptr_entry *results = vmalloc(max_res * sizeof(*results));
    if (!results) return -ENOMEM;
 
    // 2. 获取目标 mm
    rcu_read_lock();
    task = pid_task(find_vpid(req->pid), PIDTYPE_PID);
    if (!task) { rcu_read_unlock(); vfree(results); return -ESRCH; }
    mm = get_task_mm(task);
    rcu_read_unlock();
    if (!mm) { vfree(results); return -ESRCH; }
 
    mmap_read_lock(mm);
 
    // 3. 预建 sorted VMA range array（fit L1 cache）
    struct { uint64_t start, end; } *vranges;
    int vcount = 0;
    {
        VMA_ITERATOR(vmi_count, mm, 0);
        for_each_vma(vmi_count, vma) {
            if (vma->vm_flags & VM_READ) vcount++;
        }
    }
    vranges = vmalloc(vcount * sizeof(*vranges));
    if (!vranges) { mmap_read_unlock(mm); mmput(mm); vfree(results); return -ENOMEM; }
    {
        int idx = 0;
        VMA_ITERATOR(vmi_fill, mm, 0);
        for_each_vma(vmi_fill, vma) {
            if (!(vma->vm_flags & VM_READ)) continue;
            vranges[idx].start = vma->vm_start;
            vranges[idx].end = vma->vm_end;
            idx++;
        }
        vcount = idx;
    }
    // vranges 已按 start 排序（VMA iterator 天然有序）
 
    // 4. 指针收集
    VMA_ITERATOR(vmi, mm, 0);
    for_each_vma(vmi, vma) {
        unsigned long addr, end;
        if (found >= max_res) break;
        if (!(vma->vm_flags & VM_READ)) continue;
        if (vma->vm_flags & (VM_IO | VM_PFNMAP)) continue;
        if ((req->flags & PTRSCAN_WRITABLE_ONLY) && !(vma->vm_flags & VM_WRITE))
            continue;
 
        end = vma->vm_end;
        for (addr = vma->vm_start; addr < end && found < max_res; addr += PAGE_SIZE) {
            struct pte_result pr;
            void *kaddr;
            unsigned int off;
 
            if (signal_pending(current)) goto out_unlock;
 
            pr = walk_pte_safe(mm, vma, addr);
            if (!pr.page) continue;
 
            get_page(pr.page);
            if (pr.ptep) pte_unmap(pr.ptep);
 
            kaddr = kmap_local_page(pr.page);
 
            for (off = 0; off + 8 <= PAGE_SIZE; off += 8) {
                uint64_t val = *(uint64_t *)(kaddr + off);
                uint64_t clean = untagged_addr(val);
 
                if (!clean || clean >= TASK_SIZE) continue;
 
                // 二分查找 sorted VMA array（O(log N)，N~500，全在 L1）
                int lo = 0, hi = vcount - 1;
                bool valid = false;
                while (lo <= hi) {
                    int mid = (lo + hi) / 2;
                    if (clean < vranges[mid].start) hi = mid - 1;
                    else if (clean >= vranges[mid].end) lo = mid + 1;
                    else { valid = true; break; }
                }
 
                if (valid && found < max_res) {
                    results[found].source = (addr & PAGE_MASK) + off;
                    results[found].target = clean;
                    found++;
                }
            }
 
            kunmap_local(kaddr);
            put_page(pr.page);
 
            // 每 256 页 yield
            if (((addr >> PAGE_SHIFT) & 0xFF) == 0)
                cond_resched();
        }
    }
 
out_unlock:
    mmap_read_unlock(mm);
 
    // 5. 一次性 copy_to_user（unlock 后）
    if (found > 0) {
        if (copy_to_user((void __user *)req->result_buf, results,
                         found * sizeof(*results)))
            ret = -EFAULT;
    }
 
    req->result_count = found;
    mmput(mm);
    vfree(vranges);
    vfree(results);
    return ret;
}

Request:
  [1 byte]  0xD6
  [4 bytes] pid
  [8 bytes] target_addr
  [4 bytes] max_depth (1-16)
  [4 bytes] max_offset (typically 4095)
  [4 bytes] flags (PTRSCAN_*)
  [4 bytes] max_chains (0 = 10000)

Response:
  [4 bytes] status (0=ok)
  [4 bytes] module_count
  per module:
    [4 bytes] name_len
    [name_len bytes] name
    [8 bytes] base_addr
  [4 bytes] chain_count
  per chain:
    [4 bytes] depth
    [2 bytes] module_index (0xFFFF = not static)
    [8 bytes] base_offset (file-relative, uint64)
    [depth × 4 bytes] offsets[] (int32, signed)

#define MAX_LEVEL_WIDTH 50000
#define VISITED_SLOTS   65536
#define VISITED_MASK    (VISITED_SLOTS - 1)
 
uint64_t visited[VISITED_SLOTS];  // open-addressing hash set
int visited_count = 0;
 
bool visited_check_add(uint64_t addr) {
    uint32_t h = (uint32_t)(addr * 0x9E3779B97F4A7C15ULL >> 48);
    for (int i = 0; i < 8; i++) {  // linear probe, max 8
        uint32_t slot = (h + i) & VISITED_MASK;
        if (visited[slot] == addr) return true;   // already seen
        if (visited[slot] == 0) {
            visited[slot] = addr;
            visited_count++;
            return false;  // newly added
        }
    }
    return false;  // table full, allow through
}
 
// BFS main loop
for (int level = 0; level < max_depth && chain_count < max_chains; level++) {
    nxt_count = 0;
    for (int i = 0; i < cur_count && chain_count < max_chains; i++) {
        uint64_t find = cur_level[i].addr;
        uint64_t lo = (find > max_offset) ? find - max_offset : 0;
 
        // binary search lower_bound in sorted pairs
        int left = lower_bound(pairs, pair_count, lo);
 
        for (int j = left; j < pair_count && pairs[j].target <= find; j++) {
            uint64_t src = pairs[j].source;
 
            // DEDUP
            if (visited_check_add(src)) continue;
 
            int32_t offset = (int32_t)(find - pairs[j].target);
 
            // static check (binary search sorted modules)
            int mod_idx = find_module_bsearch(snap, src);
 
            if (mod_idx >= 0 && chain_count < max_chains) {
                // emit chain
                chains[chain_count].depth = level + 1;
                chains[chain_count].module_idx = mod_idx;
                chains[chain_count].base_offset = src - snap->entries[mod_idx].base
                                                  + snap->entries[mod_idx].file_offset;
                memcpy(chains[chain_count].offsets, cur_level[i].offsets,
                       level * sizeof(int32_t));  // 只复制已有的 depth 层
                chains[chain_count].offsets[level] = offset;
                chain_count++;
            }
 
            // push to next level
            if (nxt_count < MAX_LEVEL_WIDTH) {
                nxt_level[nxt_count].addr = src;
                nxt_level[nxt_count].depth = level + 1;
                memcpy(nxt_level[nxt_count].offsets, cur_level[i].offsets,
                       level * sizeof(int32_t));
                nxt_level[nxt_count].offsets[level] = offset;
                nxt_count++;
            }
        }
    }
    // swap
    struct bfs_node *tmp = cur_level;
    cur_level = nxt_level;
    nxt_level = tmp;
    cur_count = nxt_count;
}

entry = AddrEntry(
    address=0,
    desc="ptrscan",
    vtype="4 Bytes",
    is_pointer=True,
    base_addr_str=f"{mod_name}+0x{base_offset:X}",  # FILE-RELATIVE offset
    pointer_offsets=offsets,  # BFS 原始输出，不 reverse
)
self.pointer_selected.emit(entry)