Hot Path Vulkan Surface Coverage Index

Vulkan Surface Coverage Index and Negative Overlap Cache

Lifecycle: Performance - Unproven · Type: Prepared index
State: Source-backed; runtime value is not established.

Status: Source-backed metadata-index candidate; not implemented and not benchmarked.

Reviewed source: 322986f4c5502b3fa887a9605ac8cd88e9b2c579

Scope: Repeated surface-list scans used by texture and vertex coherency checks.

Vulkan texture and vertex paths repeatedly ask whether a guest-memory range overlaps any tracked render surface. Current helpers walk the surface list until they find an overlap—or inspect the complete list to prove that none exists.

This candidate makes the common negative answer cheap while preserving the existing exact checks and all dirty/readback behavior.

Why this is applicable

pgraph_vk_surface_overlaps_range() iterates tracked surfaces and tests their address intervals. pgraph_vk_download_surfaces_in_range_if_dirty() performs a similar scan and invokes required readback for overlapping dirty surfaces.

These helpers are used by texture preparation and vertex upload/coherency paths. Existing shortcut pages correctly treat surface overlap as a protected invariant. None currently prepares an index that can reject definitely non-overlapping ranges before the list scan.

Why it may help

Potentially avoided work includes:

• full surface-list scans for ordinary texture/vertex RAM;
• repeated interval comparisons for identical or nearby negative ranges;
• repeated traversal overhead when the tracked surface set changes rarely;
• extra cache misses from walking surface objects unrelated to the query.

The opportunity depends on:

queries
× negative-query percentage
× average surfaces examined per negative query

A surface index is not useful merely because the helper exists; counters must show that negative scans are frequent and nontrivial.

Current flow

flowchart TD
    A[Texture or vertex range query] --> B[Walk tracked surface list]
    B --> C{Current surface overlaps range?}
    C -->|Yes| D[Return overlap or inspect dirtiness/read back]
    C -->|No| E{More surfaces?}
    E -->|Yes| B
    E -->|No| F[Prove no overlap]

Loading

Candidate stage 1: conservative page coverage

flowchart TD
    A[Surface inserted, removed or resized] --> B[Update per-page coverage counts]
    C[Range query] --> D[Inspect coverage summary for spanned pages]
    D -->|No covered page| E[Return definitely no overlap]
    D -->|Any covered page| F[Run existing exact surface-list checks]
    F --> G[Return exact overlap/readback result]

Loading

The summary may produce false positives, which only fall back to current behavior. It must never produce false negatives.

Use coverage counts or equivalent ownership tracking. A boolean that is cleared when one surface disappears is unsafe when another surface still covers the same page.

Candidate stage 2: exact indexed queries

If page coverage proves useful but positive/fuzzy queries remain expensive, maintain an interval index keyed by surface start/end.

A correct interval structure must account for interval ends. Sorting only by start address and checking the nearest entry is insufficient because a large earlier surface can enclose a later query.

A smaller alternative is a negative-result cache:

(start, length, surface-footprint generation) -> no overlap

The generation changes when membership or address footprint changes—not merely when pixels are redrawn.

Separate footprint from content state

The index answers only:

Can any tracked surface occupy this address range?

It does not answer:

• whether the overlapping surface is dirty;
• whether a GPU-to-RAM readback is required;
• whether upload is pending;
• whether a surface is compatible with texture use;
• whether the current surface contents match guest RAM.

Finding no footprint overlap can safely skip exact surface work. Finding an overlap still requires the existing live content/lifetime checks.

Emulation boundary

The guest observes coherent texture, vertex and surface memory. It does not observe whether xemu proves non-overlap by a list scan, page summary or interval index.

Correctness requires that every true overlap still reaches all existing ordering, readback, dirty-publication and lifetime logic.

Seen in the wild

General memory-manager precedent: page-coverage summaries, interval trees and generation-keyed negative caches are common ways to reject address-range conflicts before expensive exact processing.

Internal xemu precedent: dirty-memory clients already summarize guest writes at page granularity and then perform more specific work when needed. The proposed coverage summary follows the same conservative pattern but tracks host surface footprints rather than content dirtiness.

Code and ownership map

Area	Role
vk/surface.c::pgraph_vk_surface_overlaps_range()	Current exact footprint scan
pgraph_vk_download_surfaces_in_range_if_dirty()	Current exact scan plus required readback
Surface create/destroy/resize paths	Must update footprint metadata
Texture binding	Consumer of overlap proof
Vertex upload/readback	Consumer of overlap and dirty readback
Renderer thread	Natural owner of surface list and index mutations

Evidence and counters

surface_overlap_queries
surface_overlap_negative_queries
surface_overlap_positive_queries
surface_objects_examined
coverage_summary_negative_hits
coverage_summary_maybe_hits
exact_scans_after_summary
negative_cache_hits
surface_footprint_generation_changes
surface_readbacks_triggered

Key measures:

average surfaces examined per query
negative fast-reject rate
exact scan reduction
index update cost per surface lifetime event

Risks

• False negative after insert, resize, alias change or removal bookkeeping bug.
• Coverage underflow when overlapping surfaces share pages.
• Overflow/rounding errors at page and range ends.
• Treating footprint generation as content generation.
• Caching a negative answer across renderer reset or snapshot restore.
• Index maintenance or cache lookup costing more than short-list scans.
• Duplicating surface ownership state and allowing the copies to diverge.
• Using the index to skip required dirty/readback processing after a positive match.

Qualification

1. Add a pure interval/page-coverage helper with inclusive/exclusive boundary tests.
2. Test overlapping surfaces sharing pages and removal in every order.
3. Test unaligned starts/ends, zero/overflow guards and full-VRAM edge ranges.
4. Test surface resize/rebind/recreation and snapshot restore.
5. Prove every summary negative agrees with the exact scan.
6. Compare positive query results and dirty readback decisions with current behavior.
7. Exercise texture, palette, vertex and scanout consumers.
8. Run Vulkan validation and surface/vertex XISO oracles.
9. Measure list length, negative rate and surfaces examined before choosing page summary versus interval tree.
10. Keep stage 1 and stage 2 as separate experiments.

Disposition

Applicable, but evidence should choose the data structure. Begin with counters and a conservative page-coverage summary; do not install a complex interval tree before proving surface-list scans are a material cost.

Related pages

• Hot-Path Shortcuts
• Clean Texture Stages
• Prepared Vertex Layouts
• Bounded Vertex Uploads
• Memory & DMA
• Vulkan Renderer

Full technical reference

Primary reference: This subject page is the design and research reference for Surface Coverage Index. Pull requests are implementation/test history only.
Lifecycle: Performance - Unproven · Mechanism: Conservative spatial metadata/index
Reviewed source: 322986f4c5502b3fa887a9605ac8cd88e9b2c579 · Acceptance class: intended exact or behavior-preserving for its admitted scope

1. Scope

Answer common no-overlap range queries without walking every surface, while retaining exact checks for positive or ambiguous cases.

This entry remains Unproven: the source path and opportunity are concrete, but no accepted xemu runtime result has established that the candidate improves representative workloads. The page defines what must be bypassed, what remains mandatory, and how the hypothesis can be rejected.

2. Source seams

File / function	Role
hw/xbox/nv2a/pgraph/vk/surface.c	pgraph_vk_surface_overlaps_range() and download_surfaces_in_range_if_dirty()
hw/xbox/nv2a/pgraph/vk/texture.c	surface-overlap coherency checks
hw/xbox/nv2a/pgraph/vk/vertex.c	vertex-range dirty-surface checks

3. Current execution path

flowchart TD
    N0["Range query"]
    N1["Walk surface list"]
    N0 --> N1
    N2["Check each (start,end) interval"]
    N1 --> N2
    N3["Return overlap or none"]
    N2 --> N3
    N4["Possibly repeat for texture/vertex preparation"]
    N3 --> N4

Loading

4. Candidate execution path

flowchart TD
    N0["Surface insert/remove/resize updates page coverage"]
    N1["Range query checks covered pages"]
    N0 --> N1
    N2["No covered pages: return no overlap"]
    N1 --> N2
    N3["Covered/ambiguous: run exact existing scan"]
    N2 --> N3

Loading

5. Why it may help

Texture and vertex memory often has no surface overlap. A conservative page summary can turn repeated negative scans into a few metadata checks. It must allow false positives but never false negatives.

6. Work removed

• Full surface-list scans for definitely empty ranges
• Repeated negative overlap work across nearby queries

7. Work that remains mandatory

• Exact scan for positive/ambiguous pages
• Dirty-content checks and downloads
• Surface lifetime/content state
• Range overflow validation

8. Implementation sketch

if (!coverage_any(pg->surface_coverage, start, size)) {
    stats.surface_overlap_fast_negative++;
    return false;
}
stats.surface_overlap_exact_scans++;
return pgraph_vk_surface_overlaps_range_reference(pg, start, size);

The sketch defines the intended boundary; it is not a complete patch and does not replace source review, ownership design, or focused tests.

9. Correctness contract

• Coverage metadata may over-report but must never under-report.
• Counts/ownership are required when overlapping surfaces share pages; a boolean cannot be cleared when only one surface disappears.
• Address overflow and zero-length semantics must match the reference.
• Content cleanliness is separate from footprint coverage.

10. State, ownership, invalidation, and fallback

Coverage is updated with surface footprint/lifetime changes, not every draw. A generation can key a recent negative cache. Reset, restore, scale/shape changes, insertion, removal, and resize update or rebuild metadata.

The maintained reference path remains the fallback whenever admission, capability, lifetime, or validation is uncertain. A fast result with an unproven dependency is not acceptable as an exact optimization.

11. Advantages

• Cheap common negative result
• Preserves exact positive logic
• Useful counters show whether an interval tree is warranted later
• Benefits texture and vertex coherency paths

12. Costs and failure modes

• Metadata maintenance overhead
• False negatives would be severe correctness bugs
• Large page granularity may produce many false positives
• Complex exact indexes can exceed short-list scan cost

13. Evidence counters

Counters must be cheap, subsystem-owned, and snapshotted outside the hot loop. Record at least:

• range_queries
• fast_negative_queries
• covered_page_queries
• exact_surface_scans
• surfaces_examined
• coverage_updates
• false_positive_rate
• query_cpu_us

A local reduction is not enough. Evidence must connect route reachability and removed work to fixed guest progress, CPU/GPU time where applicable, and p95/p99 behavior.

14. Qualification matrix

• Randomized differential ranges against reference scan
• Overlapping surfaces and shared pages
• Insert/remove one of several overlaps
• Large enclosing intervals
• Boundary/overflow cases
• Resize/scale/reset/snapshot
• Texture and vertex callers
• Stress many surface records

Correctness runs may use validation layers, detailed comparisons, and fault injection. Performance acceptance must use optimized Release builds with matching symbols and minimal instrumentation.

15. Acceptance rule

Promote the conservative summary when differential tests prove no false negatives and negative-query frequency/cost is material.

16. Rejection rule

Reject or stop before an exact tree if surface counts are small, positives dominate, or metadata maintenance exceeds saved scans.

17. Related architecture and history

Vulkan-Renderer · Performance-Unproven · Hot-Path-Vulkan-Direct-Surface-Sampling · Vulkan-GPU-Resident-Surface-Consumers

PR pages may be linked as supporting evidence, but they are not substitutes for this reference.