# UNDF: UNDF-2026-000000273
# sdl3-0001: SDL3 GPU TRACK_RESOURCE — O(N²) linear dedup in command buffer resource tracking (Vulkan + D3D12)

## CWE-407 — Algorithmic Complexity

| Field | Value |
|-------|-------|
| ID | sdl3-0001 |
| Severity | HIGH |
| Ecosystem | SDL3 (Simple DirectMedia Layer 3) |
| Package | SDL_gpu — Vulkan + D3D12 backends |
| Files | `src/gpu/vulkan/SDL_gpu_vulkan.c`, `src/gpu/d3d12/SDL_gpu_d3d12.c`, `src/gpu/metal/SDL_gpu_metal.m` |
| Lines | Vulkan: 2439–2454 (macro); D3D12: 2038–2055 (macro) |
| Complexity | O(N²) per command buffer with N unique bound resources |
| Hot path | Every draw call that binds textures, buffers, samplers, or pipelines |

## Background

SDL3's GPU API (added in SDL 3.2) provides a cross-platform GPU abstraction
over Vulkan, D3D12, and Metal.  Each command buffer records GPU commands and
tracks which GPU resources it references, incrementing their reference counts
to prevent premature destruction.

At command buffer submission time, the tracked resource lists are walked to
decrement reference counts.  Duplicate tracking must be prevented because
double-decrement would corrupt reference counts.

## Defect

Both the Vulkan and D3D12 backends implement resource tracking via an identical
`TRACK_RESOURCE` macro that performs a **full linear scan** of all already-tracked
resources before adding a new one:

**Vulkan backend** (`src/gpu/vulkan/SDL_gpu_vulkan.c:2439`):

```c
#define TRACK_RESOURCE(resource, type, array, count, capacity, refcountvar)  \
    for (Sint32 i = commandBuffer->count - 1; i >= 0; i -= 1) { \
        if (commandBuffer->array[i] == resource) {              \
            return;                                             \
        }                                                       \
    }                                                           \
                                                                \
    if (commandBuffer->count == commandBuffer->capacity) {      \
        commandBuffer->capacity += 1;                           \
        commandBuffer->array = SDL_realloc(                     \
            commandBuffer->array,                               \
            commandBuffer->capacity * sizeof(type));            \
    }                                                           \
    commandBuffer->array[commandBuffer->count] = resource;      \
    commandBuffer->count += 1;                                  \
    SDL_AtomicIncRef(&refcountvar)
```

**D3D12 backend** (`src/gpu/d3d12/SDL_gpu_d3d12.c:2038`):

```c
#define TRACK_RESOURCE(resource, type, array, count, capacity) \
    Uint32 i;                                                  \
                                                               \
    for (i = 0; i < commandBuffer->count; i += 1) {            \
        if (commandBuffer->array[i] == resource) {             \
            return;                                            \
        }                                                      \
    }                                                          \
    ...
```

This macro is instantiated for **five resource types** per backend:

| Resource type | Vulkan Track fn | D3D12 Track fn |
|---------------|-----------------|----------------|
| Texture | `VULKAN_INTERNAL_TrackTexture` | `D3D12_INTERNAL_TrackTexture` |
| Buffer | `VULKAN_INTERNAL_TrackBuffer` | `D3D12_INTERNAL_TrackBuffer` |
| Sampler | `VULKAN_INTERNAL_TrackSampler` | `D3D12_INTERNAL_TrackSampler` |
| Graphics Pipeline | `VULKAN_INTERNAL_TrackGraphicsPipeline` | `D3D12_INTERNAL_TrackGraphicsPipeline` |
| Compute Pipeline | `VULKAN_INTERNAL_TrackComputePipeline` | `D3D12_INTERNAL_TrackComputePipeline` |

These are called in `VULKAN_BindVertexSamplers`, `VULKAN_BindVertexStorageTextures`,
`VULKAN_BindVertexStorageBuffers`, `VULKAN_BindFragmentSamplers`, and many more —
**55+ call sites total** across the Vulkan backend alone.

Each call to a `Bind*` function triggers a TrackResource call that scans all
previously tracked resources of that type.  For a complex scene that binds N
distinct textures across its draw calls, the total cost is:

```
sum(1 + 2 + 3 + ... + N) = N*(N+1)/2 = O(N²)
```

A render pass that samples from 64 textures pays 64×63/2 = 2016 comparisons
just for texture tracking, plus equivalent costs for buffers, samplers, and
pipelines.  In practice a modern 3D scene may use 200–1000+ distinct resources
per frame.

## Fix

Replace the linear dedup scan with a hash set.  SDL already has a hash map
implementation (`SDL_hashtable.c`).  Since the resource pointers are unique
per-object, pointer identity is a sufficient hash key.

**Option A — per-resource-type hash set alongside the array (O(1) dedup):**

```c
// Add to VulkanCommandBuffer struct:
SDL_HashTable *usedTextureSet;
SDL_HashTable *usedBufferSet;
SDL_HashTable *usedSamplerSet;
// ... etc.

// Replace TRACK_RESOURCE macro:
#define TRACK_RESOURCE(resource, type, array, count, capacity, refcountvar) \
    if (SDL_InsertIntoHashTable(commandBuffer->array##Set,                  \
                                (const void *)(uintptr_t)(resource),        \
                                (const void *)(uintptr_t)(resource),        \
                                false)) {                                   \
        /* not a duplicate — inserted successfully */                       \
        if (commandBuffer->count == commandBuffer->capacity) {              \
            commandBuffer->capacity += 1;                                   \
            commandBuffer->array = SDL_realloc(                             \
                commandBuffer->array,                                       \
                commandBuffer->capacity * sizeof(type));                    \
        }                                                                   \
        commandBuffer->array[commandBuffer->count] = resource;              \
        commandBuffer->count += 1;                                          \
        SDL_AtomicIncRef(&refcountvar);                                     \
    }
```

`SDL_InsertIntoHashTable` with `overwrite=false` returns `true` on first
insertion and `false` on duplicate, providing O(1) amortized membership test.

**Option B — single unified resource set (all types in one table):**

Use a single `SDL_HashTable *usedResourceSet` keyed by `(void *)resource`.
Avoids the per-type overhead at the cost of losing type separation.

**Option C — sorted insertion with binary search:**

Since resources are added monotonically per command buffer, a sorted array
with `bsearch` gives O(log N) amortized cost.  Simpler to implement than a
hash table, still dramatically better than O(N).

The Vulkan backend already uses `SDL_HashTable` in `VULKAN_INTERNAL_CreatePipeline`
for the pipeline cache, confirming the pattern is available.

## Speedup

| N (unique resources per command buffer) | Before (ops) | After (ops) | Speedup |
|-----------------------------------------|--------------|-------------|---------|
| 16 | 136 | 16 | 8.5× |
| 64 | 2,080 | 64 | 32.5× |
| 256 | 32,896 | 256 | 128× |
| 1,024 | 524,800 | 1,024 | 512× |

For a typical mid-complexity 3D scene with N ≈ 64 unique resources per frame:
32× reduction in resource-tracking overhead per frame.  At N = 256 (a heavy
scene with many textures and compute passes), the speedup reaches 128×.

## Scope

All three GPU backends carry the identical defect:

- **Vulkan** (`src/gpu/vulkan/SDL_gpu_vulkan.c:2439`) — reverse scan
- **D3D12** (`src/gpu/d3d12/SDL_gpu_d3d12.c:2038`) — forward scan
- **Metal** (`src/gpu/metal/SDL_gpu_metal.m:43`) — forward scan

The macro body is structurally identical in all three; only the refcount
field name differs.

This defect was introduced when the SDL3 GPU API was added and affects all
applications using `SDL_GPU*` functions for 3D rendering, compute, or GPU-
accelerated 2D.  The SDL2 renderer backend is not affected.
