texture_cache: back large sparse 2D images by sparse block

Mario Kart World's nine world-sized masks (R8 16384x16384, RG16 and
R16 8192x8192, 170-341 MB each) live in sparse regions the game maps
its own memory into, a few MiB of each. Since a mapped tile counts as
written, the texture cache backed and uploaded each mask in full: about
2.9 GB of device memory, and a whole-mask upload for every tile the
game streamed in.

Such images (single layer, one texel per block, colour, in a sparse
region, 32 MiB or more) are now unbacked SparseTiles images. The
texture cache records the guest ranges written to them; Image::BindTiles
gives the host sparse blocks under those ranges memory, and only those
rectangles are unswizzled, a row of whole GOB blocks at a time, and
uploaded. A new image starts with the tiles the game maps there (nx2:gpu
216 now records them per 64 KiB), or the written blocks where it maps
none. Unmapped tiles keep their blocks and are loaded as zeros.

Checked against the full unswizzle on 400 ordinary game images (row
padding, mip chains, odd sizes): no row differs. Not on AMD drivers,
which cannot sample images with unbound memory.

Mario Kart World title screen, 150 s, against backing the masks whole:
dedicated VRAM 6.6 -> 6.2 GB, shared 1.0 -> 0.3 GB, peak 8.2 -> 6.9 GB.

6 files changed, 315 insertions, 0 deletions

diff --git a/src/video_core/texture_cache/image_base.h b/src/video_core/texture_cache/image_base.h
index 04254fb417..878c229953 100644
--- a/src/video_core/texture_cache/image_base.h
+++ b/src/video_core/texture_cache/image_base.h
@@ -56,6 +56,10 @@ enum class ImageFlagBits : u32 {
     /// A large array over Switch 2 sparse blocks: unbacked, each layer gets device memory when
     /// something is written to it (Image::BindLayers) and only those layers are uploaded.
     SparseLayers = 1 << 22,
+    /// A large single image over Switch 2 sparse blocks: unbacked, each host sparse block gets
+    /// device memory when the guest memory under it can hold data (Image::BindTiles), and only
+    /// the parts written are uploaded.
+    SparseTiles = 1 << 23,
 };
 DECLARE_ENUM_FLAG_OPERATORS(ImageFlagBits)
 
@@ -108,6 +112,9 @@ struct ImageBase {
     /// Large layered images uploaded by layer: one bit per layer written since the last upload
     /// while CpuModified. Empty while CpuModified means the whole image.
     std::vector<u64> dirty_layers;
+    /// SparseTiles images: the guest byte ranges (offset, size) written since the last upload while
+    /// CpuModified. Empty while CpuModified means all of it that can hold data.
+    std::vector<std::pair<u64, u64>> dirty_ranges;
     u64 scale_tick = 0;
     bool has_scaled = false;
 
diff --git a/src/video_core/texture_cache/texture_cache.h b/src/video_core/texture_cache/texture_cache.h
index 3b783fc6c6..4b93cd135b 100644
--- a/src/video_core/texture_cache/texture_cache.h
+++ b/src/video_core/texture_cache/texture_cache.h
@@ -729,6 +729,10 @@ void TextureCache<P>::WriteMemory(DAddr cpu_addr, size_t size) {
             image.flags |= ImageFlagBits::CpuModified | ImageFlagBits::Remapped;
             return;
         }
+        if (True(image.flags & ImageFlagBits::SparseTiles)) {
+            MarkRangeWritten(image, cpu_addr, size);
+            return;
+        }
         if (UploadsByLayer(image)) {
             MarkLayersWritten(image, cpu_addr, size);
             return;
@@ -1316,6 +1320,10 @@ void TextureCache<P>::RefreshContents(Image& image, ImageId image_id) {
         RefreshSparseLayers(image);
         return;
     }
+    if (True(image.flags & ImageFlagBits::SparseTiles)) {
+        RefreshSparseTiles(image);
+        return;
+    }
     if (!image.dirty_layers.empty() && UploadWrittenLayers(image)) {
         runtime.InsertUploadMemoryBarrier();
         return;
@@ -1401,6 +1409,63 @@ void TextureCache<P>::MarkLayersWritten(Image& image, DAddr cpu_addr, size_t siz
 }
 
 template <class P>
+void TextureCache<P>::MarkRangeWritten(Image& image, DAddr cpu_addr, size_t size) {
+    if (True(image.flags & ImageFlagBits::CpuModified) && image.dirty_ranges.empty()) {
+        return; // all of it is dirty already
+    }
+    const DAddr begin = (std::max<DAddr>)(cpu_addr, image.cpu_addr);
+    const DAddr end = (std::min<DAddr>)(cpu_addr + size, image.cpu_addr + image.guest_size_bytes);
+    if (end <= begin) {
+        return;
+    }
+    image.flags |= ImageFlagBits::CpuModified;
+    image.dirty_ranges.emplace_back(begin - image.cpu_addr, end - begin);
+}
+
+template <class P>
+void TextureCache<P>::RefreshSparseTiles(Image& image) {
+    if constexpr (requires { &Image::BindTiles; }) {
+        // The ranges written since the last upload, or, for a new image, all of it that can hold
+        // data (the tiles the game maps there, or the blocks written).
+        std::vector<std::pair<u64, u64>> ranges = std::move(image.dirty_ranges);
+        image.dirty_ranges.clear();
+        if (ranges.empty()) {
+            ranges = Tegra::Nx2SparseDataRanges(image.gpu_addr, image.guest_size_bytes);
+        }
+        const std::vector<LevelRect> rects =
+            SparseTileRects(image.info, ranges, image.SparseTileWidth(), image.SparseTileHeight(),
+                            image.SparseTailLevel());
+        if (rects.empty() || !BindSparseTiles(image, rects)) {
+            runtime.TransitionImageLayout(image);
+            return;
+        }
+        const size_t bytes = UnswizzledRectsBytes(image.info, rects);
+        auto staging = runtime.UploadStagingBuffer(bytes);
+        const std::vector<BufferImageCopy> copies =
+            UnswizzleImageRects(*gpu_memory, image.gpu_addr, image.info, rects, staging.mapped_span);
+        image.UploadMemory(staging, copies);
+        runtime.InsertUploadMemoryBarrier();
+        ++images_uploaded;
+        uploaded_bytes += bytes;
+    }
+}
+
+template <class P>
+bool TextureCache<P>::BindSparseTiles(Image& image, std::span<const LevelRect> rects) {
+    if constexpr (requires { &Image::BindTiles; }) {
+        const u64 bound_bytes = ImageMemoryBytes(image);
+        const bool bound = image.BindTiles(rects);
+        // RegisterImage counts what an image has bound by then; later binds are added here.
+        if (True(image.flags & ImageFlagBits::Registered)) {
+            total_used_memory += ImageMemoryBytes(image) - bound_bytes;
+        }
+        return bound;
+    } else {
+        return false;
+    }
+}
+
+template <class P>
 bool TextureCache<P>::UploadWrittenLayers(Image& image) {
     if constexpr (requires { &Runtime::AccelerateImageUploadLayers; }) {
         const u32 num_layers = static_cast<u32>(image.info.resources.layers);
diff --git a/src/video_core/texture_cache/texture_cache_base.h b/src/video_core/texture_cache/texture_cache_base.h
index 94102cd261..f27e237cfa 100644
--- a/src/video_core/texture_cache/texture_cache_base.h
+++ b/src/video_core/texture_cache/texture_cache_base.h
@@ -164,6 +164,15 @@ class TextureCache : public VideoCommon::ChannelSetupCaches<TextureCacheChannelI
     /// Records the layers a write of [cpu_addr, +size) touches.
     void MarkLayersWritten(Image& image, DAddr cpu_addr, size_t size);
 
+    /// SparseTiles images: notes a written range, uploaded with the next refresh.
+    void MarkRangeWritten(Image& image, DAddr cpu_addr, size_t size);
+
+    /// SparseTiles images: binds and uploads the parts written since the last upload.
+    void RefreshSparseTiles(Image& image);
+
+    /// Image::BindTiles, counting what it binds in total_used_memory.
+    bool BindSparseTiles(Image& image, std::span<const LevelRect> rects);
+
     /// Uploads the image's dirty layers. False when it needs a full upload instead.
     bool UploadWrittenLayers(Image& image);
 
diff --git a/src/video_core/texture_cache/types.h b/src/video_core/texture_cache/types.h
index ecacd8c6bd..9e541d6afc 100644
--- a/src/video_core/texture_cache/types.h
+++ b/src/video_core/texture_cache/types.h
@@ -132,6 +132,15 @@ struct ImageCopy {
     Extent3D extent;
 };
 
+/// A rectangle of one mip level, in texels.
+struct LevelRect {
+    s32 level;
+    u32 x;
+    u32 y;
+    u32 width;
+    u32 height;
+};
+
 struct BufferImageCopy {
     size_t buffer_offset;
     size_t buffer_size;
diff --git a/src/video_core/texture_cache/util.cpp b/src/video_core/texture_cache/util.cpp
index ef34019a08..0e1acba813 100644
--- a/src/video_core/texture_cache/util.cpp
+++ b/src/video_core/texture_cache/util.cpp
@@ -929,6 +929,210 @@ boost::container::small_vector<BufferImageCopy, 16> UnswizzleImage(Tegra::Memory
     return copies;
 }
 
+namespace {
+// One level of a single-layer 2D block-linear image of 1x1-texel blocks, laid out as
+// UnswizzleImage reads it: rows of blocks, each block one GOB wide and 2^block_height GOBs tall.
+struct BlockLinearLevel {
+    u32 offset;         ///< Into the image
+    u32 width;          ///< Texels
+    u32 height;
+    u32 block_height;   ///< Log2 of the GOBs a block is tall
+    u32 block_texels;   ///< Texels across a block
+    u32 block_rows;     ///< Texel rows in a block
+    u32 block_bytes;
+    u32 blocks_per_row;
+};
+
+std::vector<BlockLinearLevel> BlockLinearLevels(const ImageInfo& info) {
+    const LevelInfo level_info = MakeLevelInfo(info);
+    const u32 bpp_log2 = BytesPerBlockLog2(info.format);
+    const Extent2D gob = GobSize(bpp_log2, info.block.height, info.tile_width_spacing);
+    std::vector<BlockLinearLevel> levels;
+    u32 offset = 0;
+    for (s32 level = 0; level < info.resources.levels; ++level) {
+        const Extent3D level_size = AdjustMipSize(info.size, level);
+        const Extent3D num_tiles = AdjustTileSize(level_size, level_info.tile_size);
+        const Extent3D block =
+            AdjustMipBlockSize(num_tiles, level_info.block, level, level_info.num_levels);
+        const u32 stride_alignment = StrideAlignment(num_tiles, info.block, gob, bpp_log2);
+        const u32 stride = Common::AlignUpLog2(num_tiles.width, stride_alignment) << bpp_log2;
+        levels.push_back({
+            .offset = offset,
+            .width = level_size.width,
+            .height = level_size.height,
+            .block_height = block.height,
+            .block_texels = GOB_SIZE_X >> bpp_log2,
+            .block_rows = GOB_SIZE_Y << block.height,
+            .block_bytes = GOB_SIZE << block.height,
+            .blocks_per_row = Common::DivCeilLog2(stride, GOB_SIZE_X_SHIFT),
+        });
+        offset += CalculateLevelSize(level_info, level);
+    }
+    return levels;
+}
+
+// Rows of blocks a rectangle covers, and its blocks across.
+struct RectBlocks {
+    u32 first_row;
+    u32 last_row;
+    u32 first_block;
+    u32 num_blocks;
+};
+
+RectBlocks BlocksOf(const BlockLinearLevel& level, const LevelRect& rect) {
+    const u32 first_block = rect.x / level.block_texels;
+    return {
+        .first_row = rect.y / level.block_rows,
+        .last_row = (rect.y + rect.height - 1) / level.block_rows,
+        .first_block = first_block,
+        .num_blocks = (std::min)(Common::DivCeil(rect.width, level.block_texels),
+                                 level.blocks_per_row - first_block),
+    };
+}
+
+u32 BlockRowTexelRows(const BlockLinearLevel& level, u32 row) {
+    return (std::min)(level.block_rows, level.height - row * level.block_rows);
+}
+} // Anonymous namespace
+
+std::vector<LevelRect> SparseTileRects(const ImageInfo& info,
+                                       std::span<const std::pair<u64, u64>> ranges, u32 tile_width,
+                                       u32 tile_height, s32 tail_level) {
+    std::vector<LevelRect> rects;
+    const std::vector<BlockLinearLevel> levels = BlockLinearLevels(info);
+    const u64 image_end = CalculateLevelBytes(
+        CalculateLevelSizes(MakeLevelInfo(info), info.resources.levels), info.resources.levels);
+    for (s32 index = 0; index < static_cast<s32>(levels.size()); ++index) {
+        const BlockLinearLevel& level = levels[index];
+        const u64 level_end =
+            index + 1 < static_cast<s32>(levels.size()) ? levels[index + 1].offset : image_end;
+        const auto overlaps = [&](const std::pair<u64, u64>& range) {
+            return range.first < level_end && range.first + range.second > level.offset;
+        };
+        if (index >= tail_level) {
+            if (std::ranges::any_of(ranges, overlaps)) {
+                rects.push_back({index, 0, 0, level.width, level.height});
+            }
+            continue;
+        }
+        const u32 tiles_x = Common::DivCeil(level.width, tile_width);
+        const u32 tiles_y = Common::DivCeil(level.height, tile_height);
+        std::vector<bool> touched(size_t{tiles_x} * tiles_y);
+        for (const auto& range : ranges) {
+            if (!overlaps(range)) {
+                continue;
+            }
+            const u64 begin = (std::max<u64>)(range.first, level.offset) - level.offset;
+            const u64 end = (std::min<u64>)(range.first + range.second, level_end) - level.offset;
+            const u64 first = begin / level.block_bytes;
+            const u64 last = (end - 1) / level.block_bytes;
+            for (u64 row = first / level.blocks_per_row; row <= last / level.blocks_per_row; ++row) {
+                const u64 row_start = row * level.blocks_per_row;
+                const u64 low = (std::max)(first, row_start) - row_start;
+                const u64 high = (std::min)(last, row_start + level.blocks_per_row - 1) - row_start;
+                const u64 x0 = low * level.block_texels;
+                const u64 y0 = row * level.block_rows;
+                if (x0 >= level.width || y0 >= level.height) {
+                    continue;
+                }
+                const u64 x1 = (std::min<u64>)((high + 1) * level.block_texels, level.width);
+                const u64 y1 = (std::min<u64>)(y0 + level.block_rows, level.height);
+                for (u64 ty = y0 / tile_height; ty <= (y1 - 1) / tile_height; ++ty) {
+                    for (u64 tx = x0 / tile_width; tx <= (x1 - 1) / tile_width; ++tx) {
+                        touched[ty * tiles_x + tx] = true;
+                    }
+                }
+            }
+        }
+        for (u32 ty = 0; ty < tiles_y; ++ty) {
+            for (u32 tx = 0; tx < tiles_x;) {
+                if (!touched[size_t{ty} * tiles_x + tx]) {
+                    ++tx;
+                    continue;
+                }
+                const u32 first_tile = tx;
+                while (tx < tiles_x && touched[size_t{ty} * tiles_x + tx]) {
+                    ++tx;
+                }
+                const u32 x = first_tile * tile_width;
+                const u32 y = ty * tile_height;
+                rects.push_back({
+                    .level = index,
+                    .x = x,
+                    .y = y,
+                    .width = (std::min)(tx * tile_width, level.width) - x,
+                    .height = (std::min)(y + tile_height, level.height) - y,
+                });
+            }
+        }
+    }
+    return rects;
+}
+
+size_t UnswizzledRectsBytes(const ImageInfo& info, std::span<const LevelRect> rects) {
+    const std::vector<BlockLinearLevel> levels = BlockLinearLevels(info);
+    const u32 bpp_log2 = BytesPerBlockLog2(info.format);
+    size_t bytes = 0;
+    for (const LevelRect& rect : rects) {
+        const BlockLinearLevel& level = levels[rect.level];
+        const RectBlocks blocks = BlocksOf(level, rect);
+        for (u32 row = blocks.first_row; row <= blocks.last_row; ++row) {
+            bytes += (size_t{blocks.num_blocks * level.block_texels} << bpp_log2) *
+                     BlockRowTexelRows(level, row);
+        }
+    }
+    return bytes;
+}
+
+std::vector<BufferImageCopy> UnswizzleImageRects(Tegra::MemoryManager& gpu_memory,
+                                                 GPUVAddr gpu_addr, const ImageInfo& info,
+                                                 std::span<const LevelRect> rects,
+                                                 std::span<u8> output) {
+    const std::vector<BlockLinearLevel> levels = BlockLinearLevels(info);
+    const u32 bpp_log2 = BytesPerBlockLog2(info.format);
+    std::vector<BufferImageCopy> copies;
+    std::vector<u8> swizzled;
+    size_t output_offset = 0;
+    for (const LevelRect& rect : rects) {
+        const BlockLinearLevel& level = levels[rect.level];
+        const RectBlocks blocks = BlocksOf(level, rect);
+        const u32 width = blocks.num_blocks * level.block_texels;
+        const size_t row_bytes = size_t{blocks.num_blocks} * level.block_bytes;
+        for (u32 row = blocks.first_row; row <= blocks.last_row; ++row) {
+            // A row of whole blocks is laid out like an image of that width on its own.
+            const u32 texel_rows = BlockRowTexelRows(level, row);
+            const size_t bytes = (size_t{width} << bpp_log2) * texel_rows;
+            const GPUVAddr row_addr = gpu_addr + level.offset +
+                                      u64{row} * level.blocks_per_row * level.block_bytes +
+                                      u64{blocks.first_block} * level.block_bytes;
+            swizzled.assign(row_bytes, 0);
+            gpu_memory.ReadBlockUnsafe(row_addr, swizzled.data(), row_bytes);
+            UnswizzleTexture(output.subspan(output_offset, bytes), swizzled, 1U << bpp_log2, width,
+                             texel_rows, 1, level.block_height, 0, 0,
+                             gpu_memory.UsesNativeTiling());
+            const u32 row_y = row * level.block_rows;
+            const u32 y0 = (std::max)(rect.y, row_y);
+            const u32 y1 = (std::min)(rect.y + rect.height, row_y + texel_rows);
+            copies.push_back(BufferImageCopy{
+                .buffer_offset = output_offset + ((size_t{y0 - row_y} * width) << bpp_log2),
+                .buffer_size = bytes,
+                .buffer_row_length = width,
+                .buffer_image_height = texel_rows,
+                .image_subresource =
+                    {
+                        .base_level = rect.level,
+                        .base_layer = 0,
+                        .num_layers = 1,
+                    },
+                .image_offset = {static_cast<s32>(rect.x), static_cast<s32>(y0), 0},
+                .image_extent = {rect.width, y1 - y0, 1},
+            });
+            output_offset += bytes;
+        }
+    }
+    return copies;
+}
+
 void ConvertedLayout(const ImageInfo& info, std::span<BufferImageCopy> copies) {
     // Same offsets and sizes as ConvertImage below.
     const auto recompression = Settings::GetAstcRecompression();
diff --git a/src/video_core/texture_cache/util.h b/src/video_core/texture_cache/util.h
index 0381d2d24b..74da0f90f9 100644
--- a/src/video_core/texture_cache/util.h
+++ b/src/video_core/texture_cache/util.h
@@ -8,6 +8,8 @@
 
 #include <optional>
 #include <span>
+#include <utility>
+#include <vector>
 #include <boost/container/small_vector.hpp>
 
 #include "common/common_types.h"
@@ -72,6 +74,25 @@ struct OverlapResult {
     Tegra::MemoryManager& gpu_memory, GPUVAddr gpu_addr, const ImageInfo& info,
     std::span<const u8> input, std::span<u8> output);
 
+/// For a single-layer 2D block-linear image of 1x1-texel blocks: the host sparse blocks
+/// (tile_width x tile_height texels) that the guest byte ranges (offset, size) touch, merged into
+/// runs along x. Levels from tail_level on (the host's mip tail) come whole.
+[[nodiscard]] std::vector<LevelRect> SparseTileRects(const ImageInfo& info,
+                                                     std::span<const std::pair<u64, u64>> ranges,
+                                                     u32 tile_width, u32 tile_height,
+                                                     s32 tail_level);
+
+/// Bytes UnswizzleImageRects writes for `rects`.
+[[nodiscard]] size_t UnswizzledRectsBytes(const ImageInfo& info, std::span<const LevelRect> rects);
+
+/// Unswizzles `rects` (from SparseTileRects: on GOB columns) of a single-layer 2D block-linear
+/// image into output, reading only the guest blocks under them.
+[[nodiscard]] std::vector<BufferImageCopy> UnswizzleImageRects(Tegra::MemoryManager& gpu_memory,
+                                                               GPUVAddr gpu_addr,
+                                                               const ImageInfo& info,
+                                                               std::span<const LevelRect> rects,
+                                                               std::span<u8> output);
+
 /// Rewrites `copies` (from UnswizzleImage) to the layout ConvertImage produces, without converting.
 void ConvertedLayout(const ImageInfo& info, std::span<BufferImageCopy> copies);