Texture/Vertex/Index data cache (#132)

* Initial implementation of the texture cache

* Cache vertex and index data aswell, some cleanup

* Improve handling of the cache by storing cached ranges on a list for each page

* Delete old data from the caches automatically, ensure that the cache is cleaned when the mapping/size changes, and some general cleanup

5 files changed, 314 insertions, 110 deletions

diff --git a/Ryujinx.Graphics/Gal/OpenGL/DeleteValueCallback.cs b/Ryujinx.Graphics/Gal/OpenGL/DeleteValueCallback.cs
new file mode 100644
index 00000000..acd8d72f
--- /dev/null
+++ b/Ryujinx.Graphics/Gal/OpenGL/DeleteValueCallback.cs
@@ -0,0 +1,4 @@
+namespace Ryujinx.Graphics.Gal.OpenGL
+{
+    delegate void DeleteValue<T>(T Value);
+}
\ No newline at end of file
diff --git a/Ryujinx.Graphics/Gal/OpenGL/OGLCachedResource.cs b/Ryujinx.Graphics/Gal/OpenGL/OGLCachedResource.cs
new file mode 100644
index 00000000..06d76b8b
--- /dev/null
+++ b/Ryujinx.Graphics/Gal/OpenGL/OGLCachedResource.cs
@@ -0,0 +1,147 @@
+using System;
+using System.Collections.Generic;
+
+namespace Ryujinx.Graphics.Gal.OpenGL
+{
+    class OGLCachedResource<T>
+    {
+        public delegate void DeleteValue(T Value);
+
+        private const int MaxTimeDelta      = 5 * 60000;
+        private const int MaxRemovalsPerRun = 10;
+
+        private struct CacheBucket
+        {
+            public T Value { get; private set; }
+
+            public LinkedListNode<long> Node { get; private set; }
+
+            public long DataSize { get; private set; }
+
+            public int Timestamp { get; private set; }
+
+            public CacheBucket(T Value, long DataSize, LinkedListNode<long> Node)
+            {
+                this.Value     = Value;
+                this.DataSize  = DataSize;
+                this.Node      = Node;
+
+                Timestamp = Environment.TickCount;
+            }
+        }
+
+        private Dictionary<long, CacheBucket> Cache;
+
+        private LinkedList<long> SortedCache;
+
+        private DeleteValue DeleteValueCallback;
+
+        public OGLCachedResource(DeleteValue DeleteValueCallback)
+        {
+            if (DeleteValueCallback == null)
+            {
+                throw new ArgumentNullException(nameof(DeleteValueCallback));
+            }
+
+            this.DeleteValueCallback = DeleteValueCallback;
+
+            Cache = new Dictionary<long, CacheBucket>();
+
+            SortedCache = new LinkedList<long>();
+        }
+
+        public void AddOrUpdate(long Key, T Value, long Size)
+        {
+            ClearCacheIfNeeded();
+
+            LinkedListNode<long> Node = SortedCache.AddLast(Key);
+
+            CacheBucket NewBucket = new CacheBucket(Value, Size, Node);
+
+            if (Cache.TryGetValue(Key, out CacheBucket Bucket))
+            {
+                DeleteValueCallback(Bucket.Value);
+
+                SortedCache.Remove(Bucket.Node);
+
+                Cache[Key] = NewBucket;
+            }
+            else
+            {
+                Cache.Add(Key, NewBucket);
+            }
+        }
+
+        public bool TryGetValue(long Key, out T Value)
+        {
+            if (Cache.TryGetValue(Key, out CacheBucket Bucket))
+            {
+                Value = Bucket.Value;
+
+                return true;
+            }
+
+            Value = default(T);
+
+            return false;
+        }
+
+        public bool TryGetSize(long Key, out long Size)
+        {
+            if (Cache.TryGetValue(Key, out CacheBucket Bucket))
+            {
+                Size = Bucket.DataSize;
+
+                return true;
+            }
+
+            Size = 0;
+
+            return false;
+        }
+
+        private void ClearCacheIfNeeded()
+        {
+            int Timestamp = Environment.TickCount;
+
+            int Count = 0;
+
+            while (Count++ < MaxRemovalsPerRun)
+            {
+                LinkedListNode<long> Node = SortedCache.First;
+
+                if (Node == null)
+                {
+                    break;
+                }
+
+                CacheBucket Bucket = Cache[Node.Value];
+
+                int TimeDelta = RingDelta(Bucket.Timestamp, Timestamp);
+
+                if ((uint)TimeDelta <= (uint)MaxTimeDelta)
+                {
+                    break;
+                }
+
+                SortedCache.Remove(Node);
+
+                Cache.Remove(Node.Value);
+
+                DeleteValueCallback(Bucket.Value);
+            }
+        }
+
+        private int RingDelta(int Old, int New)
+        {
+            if ((uint)New < (uint)Old)
+            {
+                return New + (~Old + 1);
+            }
+            else
+            {
+                return New - Old;
+            }
+        }
+    }
+}
\ No newline at end of file
diff --git a/Ryujinx.Graphics/Gal/OpenGL/OGLRasterizer.cs b/Ryujinx.Graphics/Gal/OpenGL/OGLRasterizer.cs
index 5b115446..b63c8b35 100644
--- a/Ryujinx.Graphics/Gal/OpenGL/OGLRasterizer.cs
+++ b/Ryujinx.Graphics/Gal/OpenGL/OGLRasterizer.cs
@@ -44,24 +44,29 @@ namespace Ryujinx.Graphics.Gal.OpenGL
             { GalVertexAttribSize._11_11_10,    VertexAttribPointerType.Int   }  //?
         };
 
+        private int VaoHandle;
+
+        private int[] VertexBuffers;
+
+        private OGLCachedResource<int> VboCache;
+        private OGLCachedResource<int> IboCache;
+
         private struct IbInfo
         {
-            public int IboHandle;
             public int Count;
 
             public DrawElementsType Type;
         }
 
-        private int VaoHandle;
-
-        private int[] VertexBuffers;
-
         private IbInfo IndexBuffer;
 
         public OGLRasterizer()
         {
             VertexBuffers = new int[32];
 
+            VboCache = new OGLCachedResource<int>(GL.DeleteBuffer);
+            IboCache = new OGLCachedResource<int>(GL.DeleteBuffer);
+
             IndexBuffer = new IbInfo();
         }
 
@@ -92,15 +97,53 @@ namespace Ryujinx.Graphics.Gal.OpenGL
             GL.Clear(Mask);
         }
 
-        public void SetVertexArray(int VbIndex, int Stride, byte[] Buffer, GalVertexAttrib[] Attribs)
+        public bool IsVboCached(long Tag, long DataSize)
+        {
+            return VboCache.TryGetSize(Tag, out long Size) && Size == DataSize;
+        }
+
+        public bool IsIboCached(long Tag, long DataSize)
+        {
+            return IboCache.TryGetSize(Tag, out long Size) && Size == DataSize;
+        }
+
+        public void CreateVbo(long Tag, byte[] Buffer)
         {
-            EnsureVbInitialized(VbIndex);
+            int Handle = GL.GenBuffer();
+
+            VboCache.AddOrUpdate(Tag, Handle, (uint)Buffer.Length);
 
             IntPtr Length = new IntPtr(Buffer.Length);
 
-            GL.BindBuffer(BufferTarget.ArrayBuffer, VertexBuffers[VbIndex]);
+            GL.BindBuffer(BufferTarget.ArrayBuffer, Handle);
             GL.BufferData(BufferTarget.ArrayBuffer, Length, Buffer, BufferUsageHint.StreamDraw);
             GL.BindBuffer(BufferTarget.ArrayBuffer, 0);
+        }
+
+        public void CreateIbo(long Tag, byte[] Buffer)
+        {
+            int Handle = GL.GenBuffer();
+
+            IboCache.AddOrUpdate(Tag, Handle, (uint)Buffer.Length);
+
+            IntPtr Length = new IntPtr(Buffer.Length);
+
+            GL.BindBuffer(BufferTarget.ElementArrayBuffer, Handle);
+            GL.BufferData(BufferTarget.ElementArrayBuffer, Length, Buffer, BufferUsageHint.StreamDraw);
+            GL.BindBuffer(BufferTarget.ElementArrayBuffer, 0);
+        }
+
+        public void SetVertexArray(int VbIndex, int Stride, long VboTag, GalVertexAttrib[] Attribs)
+        {
+            if (!VboCache.TryGetValue(VboTag, out int VboHandle))
+            {
+                return;
+            }
+
+            if (VaoHandle == 0)
+            {
+                VaoHandle = GL.GenVertexArray();
+            }
 
             GL.BindVertexArray(VaoHandle);
 
@@ -108,7 +151,7 @@ namespace Ryujinx.Graphics.Gal.OpenGL
             {
                 GL.EnableVertexAttribArray(Attrib.Index);
 
-                GL.BindBuffer(BufferTarget.ArrayBuffer, VertexBuffers[VbIndex]);
+                GL.BindBuffer(BufferTarget.ArrayBuffer, VboHandle);
 
                 bool Unsigned =
                     Attrib.Type == GalVertexAttribType.Unorm ||
@@ -139,22 +182,14 @@ namespace Ryujinx.Graphics.Gal.OpenGL
             GL.BindVertexArray(0);
         }
 
-        public void SetIndexArray(byte[] Buffer, GalIndexFormat Format)
+        public void SetIndexArray(long Tag, int Size, GalIndexFormat Format)
         {
-            EnsureIbInitialized();
-
             IndexBuffer.Type = OGLEnumConverter.GetDrawElementsType(Format);
 
-            IndexBuffer.Count = Buffer.Length >> (int)Format;
-
-            IntPtr Length = new IntPtr(Buffer.Length);
-
-            GL.BindBuffer(BufferTarget.ElementArrayBuffer, IndexBuffer.IboHandle);
-            GL.BufferData(BufferTarget.ElementArrayBuffer, Length, Buffer, BufferUsageHint.StreamDraw);
-            GL.BindBuffer(BufferTarget.ElementArrayBuffer, 0);
+            IndexBuffer.Count = Size >> (int)Format;
         }
 
-        public void DrawArrays(int VbIndex, int First, int PrimCount, GalPrimitiveType PrimType)
+        public void DrawArrays(int First, int PrimCount, GalPrimitiveType PrimType)
         {
             if (PrimCount == 0)
             {
@@ -166,36 +201,20 @@ namespace Ryujinx.Graphics.Gal.OpenGL
             GL.DrawArrays(OGLEnumConverter.GetPrimitiveType(PrimType), First, PrimCount);
         }
 
-        public void DrawElements(int VbIndex, int First, GalPrimitiveType PrimType)
+        public void DrawElements(long IboTag, int First, GalPrimitiveType PrimType)
         {
+            if (!IboCache.TryGetValue(IboTag, out int IboHandle))
+            {
+                return;
+            }
+
             PrimitiveType Mode = OGLEnumConverter.GetPrimitiveType(PrimType);
 
             GL.BindVertexArray(VaoHandle);
 
-            GL.BindBuffer(BufferTarget.ElementArrayBuffer, IndexBuffer.IboHandle);
+            GL.BindBuffer(BufferTarget.ElementArrayBuffer, IboHandle);
 
             GL.DrawElements(Mode, IndexBuffer.Count, IndexBuffer.Type, First);
         }
-
-        private void EnsureVbInitialized(int VbIndex)
-        {
-            if (VaoHandle == 0)
-            {
-                VaoHandle = GL.GenVertexArray();
-            }
-
-            if (VertexBuffers[VbIndex] == 0)
-            {
-                VertexBuffers[VbIndex] = GL.GenBuffer();
-            }
-        }
-
-        private void EnsureIbInitialized()
-        {
-            if (IndexBuffer.IboHandle == 0)
-            {
-                IndexBuffer.IboHandle = GL.GenBuffer();
-            }
-        }
     }
 }
\ No newline at end of file
diff --git a/Ryujinx.Graphics/Gal/OpenGL/OGLTexture.cs b/Ryujinx.Graphics/Gal/OpenGL/OGLTexture.cs
index 2cbe6913..540e4735 100644
--- a/Ryujinx.Graphics/Gal/OpenGL/OGLTexture.cs
+++ b/Ryujinx.Graphics/Gal/OpenGL/OGLTexture.cs
@@ -6,18 +6,38 @@ namespace Ryujinx.Graphics.Gal.OpenGL
 {
     class OGLTexture
     {
-        private int[] Textures;
+        private class TCE
+        {
+            public int Handle;
+
+            public GalTexture Texture;
+
+            public TCE(int Handle, GalTexture Texture)
+            {
+                this.Handle  = Handle;
+                this.Texture = Texture;
+            }
+        }
+
+        private OGLCachedResource<TCE> TextureCache;
 
         public OGLTexture()
         {
-            Textures = new int[80];
+            TextureCache = new OGLCachedResource<TCE>(DeleteTexture);
         }
 
-        public void Set(int Index, GalTexture Texture)
+        private static void DeleteTexture(TCE CachedTexture)
         {
-            GL.ActiveTexture(TextureUnit.Texture0 + Index);
+            GL.DeleteTexture(CachedTexture.Handle);
+        }
 
-            Bind(Index);
+        public void Create(long Tag, byte[] Data, GalTexture Texture)
+        {
+            int Handle = GL.GenTexture();
+
+            TextureCache.AddOrUpdate(Tag, new TCE(Handle, Texture), (uint)Data.Length);
+
+            GL.BindTexture(TextureTarget.Texture2D, Handle);
 
             const int Level  = 0; //TODO: Support mipmap textures.
             const int Border = 0;
@@ -33,14 +53,24 @@ namespace Ryujinx.Graphics.Gal.OpenGL
                     Texture.Width,
                     Texture.Height,
                     Border,
-                    Texture.Data.Length,
-                    Texture.Data);
+                    Data.Length,
+                    Data);
             }
             else
             {
                 if (Texture.Format >= GalTextureFormat.Astc2D4x4)
                 {
-                    Texture = ConvertAstcTextureToRgba(Texture);
+                    int TextureBlockWidth  = GetAstcBlockWidth(Texture.Format);
+                    int TextureBlockHeight = GetAstcBlockHeight(Texture.Format);
+
+                    Data = ASTCDecoder.DecodeToRGBA8888(
+                        Data,
+                        TextureBlockWidth,
+                        TextureBlockHeight, 1,
+                        Texture.Width,
+                        Texture.Height, 1);
+
+                    Texture.Format = GalTextureFormat.A8B8G8R8;
                 }
 
                 const PixelInternalFormat InternalFmt = PixelInternalFormat.Rgba;
@@ -56,7 +86,7 @@ namespace Ryujinx.Graphics.Gal.OpenGL
                     Border,
                     Format,
                     Type,
-                    Texture.Data);
+                    Data);
             }
 
             int SwizzleR = (int)OGLEnumConverter.GetTextureSwizzle(Texture.XSource);
@@ -70,23 +100,6 @@ namespace Ryujinx.Graphics.Gal.OpenGL
             GL.TexParameter(TextureTarget.Texture2D, TextureParameterName.TextureSwizzleA, SwizzleA);
         }
 
-        private static GalTexture ConvertAstcTextureToRgba(GalTexture Texture)
-        {
-            int TextureBlockWidth  = GetAstcBlockWidth(Texture.Format);
-            int TextureBlockHeight = GetAstcBlockHeight(Texture.Format);
-
-            Texture.Data = ASTCDecoder.DecodeToRGBA8888(
-                Texture.Data,
-                TextureBlockWidth,
-                TextureBlockHeight, 1,
-                Texture.Width,
-                Texture.Height, 1);
-
-            Texture.Format = GalTextureFormat.A8B8G8R8;
-
-            return Texture;
-        }
-
         private static int GetAstcBlockWidth(GalTextureFormat Format)
         {
             switch (Format)
@@ -133,11 +146,31 @@ namespace Ryujinx.Graphics.Gal.OpenGL
             throw new ArgumentException(nameof(Format));
         }
 
-        public void Bind(int Index)
+        public bool TryGetCachedTexture(long Tag, long DataSize, out GalTexture Texture)
+        {
+            if (TextureCache.TryGetSize(Tag, out long Size) && Size == DataSize)
+            {
+                if (TextureCache.TryGetValue(Tag, out TCE CachedTexture))
+                {
+                    Texture = CachedTexture.Texture;
+
+                    return true;
+                }
+            }
+
+            Texture = default(GalTexture);
+
+            return false;
+        }
+
+        public void Bind(long Tag, int Index)
         {
-            int Handle = EnsureTextureInitialized(Index);
+            if (TextureCache.TryGetValue(Tag, out TCE CachedTexture))
+            {
+                GL.ActiveTexture(TextureUnit.Texture0 + Index);
 
-            GL.BindTexture(TextureTarget.Texture2D, Handle);
+                GL.BindTexture(TextureTarget.Texture2D, CachedTexture.Handle);
+            }
         }
 
         public static void Set(GalTextureSampler Sampler)
@@ -179,17 +212,5 @@ namespace Ryujinx.Graphics.Gal.OpenGL
 
             return false;
         }
-
-        private int EnsureTextureInitialized(int TexIndex)
-        {
-            int Handle = Textures[TexIndex];
-
-            if (Handle == 0)
-            {
-                Handle = Textures[TexIndex] = GL.GenTexture();
-            }
-
-            return Handle;
-        }
     }
 }
\ No newline at end of file
diff --git a/Ryujinx.Graphics/Gal/OpenGL/OpenGLRenderer.cs b/Ryujinx.Graphics/Gal/OpenGL/OpenGLRenderer.cs
index 69e344c7..4c4bd2ca 100644
--- a/Ryujinx.Graphics/Gal/OpenGL/OpenGLRenderer.cs
+++ b/Ryujinx.Graphics/Gal/OpenGL/OpenGLRenderer.cs
@@ -156,46 +156,54 @@ namespace Ryujinx.Graphics.Gal.OpenGL
             ActionsQueue.Enqueue(() => Rasterizer.ClearBuffers(RtIndex, Flags));
         }
 
-        public void SetVertexArray(int VbIndex, int Stride, byte[] Buffer, GalVertexAttrib[] Attribs)
+        public bool IsVboCached(long Tag, long DataSize)
         {
-            if ((uint)VbIndex > 31)
-            {
-                throw new ArgumentOutOfRangeException(nameof(VbIndex));
-            }
+            return Rasterizer.IsVboCached(Tag, DataSize);
+        }
 
-            ActionsQueue.Enqueue(() => Rasterizer.SetVertexArray(VbIndex, Stride,
-                Buffer  ?? throw new ArgumentNullException(nameof(Buffer)),
-                Attribs ?? throw new ArgumentNullException(nameof(Attribs))));
+        public bool IsIboCached(long Tag, long DataSize)
+        {
+            return Rasterizer.IsIboCached(Tag, DataSize);
         }
 
-        public void SetIndexArray(byte[] Buffer, GalIndexFormat Format)
+        public void CreateVbo(long Tag, byte[] Buffer)
         {
-            if (Buffer == null)
-            {
-                throw new ArgumentNullException(nameof(Buffer));
-            }
+            ActionsQueue.Enqueue(() => Rasterizer.CreateVbo(Tag, Buffer));
+        }
 
-            ActionsQueue.Enqueue(() => Rasterizer.SetIndexArray(Buffer, Format));
+        public void CreateIbo(long Tag, byte[] Buffer)
+        {
+            ActionsQueue.Enqueue(() => Rasterizer.CreateIbo(Tag, Buffer));
         }
 
-        public void DrawArrays(int VbIndex, int First, int PrimCount, GalPrimitiveType PrimType)
+        public void SetVertexArray(int VbIndex, int Stride, long VboTag, GalVertexAttrib[] Attribs)
         {
             if ((uint)VbIndex > 31)
             {
                 throw new ArgumentOutOfRangeException(nameof(VbIndex));
             }
 
-            ActionsQueue.Enqueue(() => Rasterizer.DrawArrays(VbIndex, First, PrimCount, PrimType));
+            if (Attribs == null)
+            {
+                throw new ArgumentNullException(nameof(Attribs));
+            }
+
+            ActionsQueue.Enqueue(() => Rasterizer.SetVertexArray(VbIndex, Stride, VboTag, Attribs));
         }
 
-        public void DrawElements(int VbIndex, int First, GalPrimitiveType PrimType)
+        public void SetIndexArray(long Tag, int Size, GalIndexFormat Format)
         {
-            if ((uint)VbIndex > 31)
-            {
-                throw new ArgumentOutOfRangeException(nameof(VbIndex));
-            }
+            ActionsQueue.Enqueue(() => Rasterizer.SetIndexArray(Tag, Size, Format));
+        }
+
+        public void DrawArrays(int First, int PrimCount, GalPrimitiveType PrimType)
+        {
+            ActionsQueue.Enqueue(() => Rasterizer.DrawArrays(First, PrimCount, PrimType));
+        }
 
-            ActionsQueue.Enqueue(() => Rasterizer.DrawElements(VbIndex, First, PrimType));
+        public void DrawElements(long IboTag, int First, GalPrimitiveType PrimType)
+        {
+            ActionsQueue.Enqueue(() => Rasterizer.DrawElements(IboTag, First, PrimType));
         }
 
         public void CreateShader(IGalMemory Memory, long Tag, GalShaderType Type)
@@ -253,19 +261,24 @@ namespace Ryujinx.Graphics.Gal.OpenGL
             ActionsQueue.Enqueue(() => Shader.BindProgram());
         }
 
-        public void SetTextureAndSampler(int Index, GalTexture Texture, GalTextureSampler Sampler)
+        public void SetTextureAndSampler(long Tag, byte[] Data, GalTexture Texture, GalTextureSampler Sampler)
         {
             ActionsQueue.Enqueue(() =>
             {
-                this.Texture.Set(Index, Texture);
+                this.Texture.Create(Tag, Data, Texture);
 
                 OGLTexture.Set(Sampler);
             });
         }
 
-        public void BindTexture(int Index)
+        public bool TryGetCachedTexture(long Tag, long DataSize, out GalTexture Texture)
+        {
+            return this.Texture.TryGetCachedTexture(Tag, DataSize, out Texture);
+        }
+
+        public void BindTexture(long Tag, int Index)
         {
-            ActionsQueue.Enqueue(() => Texture.Bind(Index));
+            ActionsQueue.Enqueue(() => Texture.Bind(Tag, Index));
         }
     }
 }
\ No newline at end of file