VkDevice: Fix sample cache hash collisions that caused spurious test failures.

Keying off a single size_t is likely to cause collisions, more so when the hash function is simple shift-xors of 3 32-bit integers.

Use a proper cache key comparision and a better hash function while we're at it.

Bug: b/137649247
Change-Id: I1e0deefb0976102714d43dcb9dcedf6aa809bf7f
Reviewed-on: https://swiftshader-review.googlesource.com/c/SwiftShader/+/34909
Tested-by: Nicolas Capens <nicolascapens@google.com>
Reviewed-by: Nicolas Capens <nicolascapens@google.com>
Reviewed-by: Chris Forbes <chrisforbes@google.com>
Kokoro-Presubmit: kokoro <noreply+kokoro@google.com>
(cherry picked from commit f046402b1480245c3c17e91131f11f066f53b289)
Reviewed-on: https://swiftshader-review.googlesource.com/c/SwiftShader/+/34928

src/Device/LRUCache.hpp

diff --git a/src/Device/LRUCache.hpp b/src/Device/LRUCache.hpp
index 083861e..e4ec2b3 100644
--- a/src/Device/LRUCache.hpp
+++ b/src/Device/LRUCache.hpp
@@ -48,7 +48,7 @@
 		Data *data;
 	};
 
-	template<class Key, class Data>
+	template<class Key, class Data, class Hasher = std::hash<Key>>
 	class LRUConstCache : public LRUCache<Key, Data>
 	{
 		using LRUBase = LRUCache<Key, Data>;
@@ -68,7 +68,7 @@
 	private:
 		void clearConstCache();
 		bool constCacheNeedsUpdate = false;
-		std::unordered_map<Key, Data> constCache;
+		std::unordered_map<Key, Data, Hasher> constCache;
 	};
 
 	// Helper class for clearing the memory of objects at construction.
@@ -189,14 +189,14 @@
 		return data;
 	}
 
-	template<class Key, class Data>
-	void LRUConstCache<Key, Data>::clearConstCache()
+	template<class Key, class Data, class Hasher>
+	void LRUConstCache<Key, Data, Hasher>::clearConstCache()
 	{
 		constCache.clear();
 	}
 
-	template<class Key, class Data>
-	void LRUConstCache<Key, Data>::updateConstCache()
+	template<class Key, class Data, class Hasher>
+	void LRUConstCache<Key, Data, Hasher>::updateConstCache()
 	{
 		if(constCacheNeedsUpdate)
 		{
@@ -214,8 +214,8 @@
 		}
 	}
 
-	template<class Key, class Data>
-	const Data& LRUConstCache<Key, Data>::queryConstCache(const Key &key) const
+	template<class Key, class Data, class Hasher>
+	const Data& LRUConstCache<Key, Data, Hasher>::queryConstCache(const Key &key) const
 	{
 		auto it = constCache.find(key);
 		static Data null = {};

src/Vulkan/VkDevice.cpp

diff --git a/src/Vulkan/VkDevice.cpp b/src/Vulkan/VkDevice.cpp
index bceb001..692db75 100644
--- a/src/Vulkan/VkDevice.cpp
+++ b/src/Vulkan/VkDevice.cpp
@@ -38,18 +38,18 @@
 
 std::shared_ptr<rr::Routine> Device::SamplingRoutineCache::query(const vk::Device::SamplingRoutineCache::Key& key) const
 {
-	return cache.query(hash(key));
+	return cache.query(key);
 }
 
 void Device::SamplingRoutineCache::add(const vk::Device::SamplingRoutineCache::Key& key, const std::shared_ptr<rr::Routine>& routine)
 {
 	ASSERT(routine);
-	cache.add(hash(key), routine);
+	cache.add(key, routine);
 }
 
 rr::Routine* Device::SamplingRoutineCache::queryConst(const vk::Device::SamplingRoutineCache::Key& key) const
 {
-	return cache.queryConstCache(hash(key)).get();
+	return cache.queryConstCache(key).get();
 }
 
 void Device::SamplingRoutineCache::updateConstCache()
@@ -57,11 +57,6 @@
 	cache.updateConstCache();
 }
 
-std::size_t Device::SamplingRoutineCache::hash(const vk::Device::SamplingRoutineCache::Key &key)
-{
-	return (key.instruction << 16) ^ (key.sampler << 8) ^ key.imageView;
-}
-
 Device::Device(const VkDeviceCreateInfo* pCreateInfo, void* mem, PhysicalDevice *physicalDevice, const VkPhysicalDeviceFeatures *enabledFeatures)
 	: physicalDevice(physicalDevice),
 	  queues(reinterpret_cast<Queue*>(mem)),

src/Vulkan/VkDevice.hpp

diff --git a/src/Vulkan/VkDevice.hpp b/src/Vulkan/VkDevice.hpp
index 742d662..ae7c21f 100644
--- a/src/Vulkan/VkDevice.hpp
+++ b/src/Vulkan/VkDevice.hpp
@@ -65,6 +65,14 @@
 			uint32_t instruction;
 			uint32_t sampler;
 			uint32_t imageView;
+
+			inline bool operator == (const Key& rhs) const;
+			inline bool operator < (const Key& rhs) const;
+
+			struct Hash
+			{
+				inline std::size_t operator()(const Key& key) const noexcept;
+			};
 		};
 
 		std::shared_ptr<rr::Routine> query(const Key& key) const;
@@ -73,10 +81,8 @@
 		rr::Routine* queryConst(const Key& key) const;
 		void updateConstCache();
 
-		static std::size_t hash(const Key &key);
-
 	private:
-		sw::LRUConstCache<std::size_t, std::shared_ptr<rr::Routine>> cache;
+		sw::LRUConstCache<Key, std::shared_ptr<rr::Routine>, Key::Hash> cache;
 	};
 
 	SamplingRoutineCache* getSamplingRoutineCache() const;
@@ -104,6 +110,24 @@
 	return DispatchableDevice::Cast(object);
 }
 
+inline bool vk::Device::SamplingRoutineCache::Key::operator == (const Key& rhs) const
+{
+	return instruction == rhs.instruction && sampler == rhs.sampler && imageView == rhs.imageView;
+}
+
+inline bool vk::Device::SamplingRoutineCache::Key::operator < (const Key& rhs) const
+{
+	return instruction < rhs.instruction || sampler < rhs.sampler || imageView < rhs.imageView;
+}
+
+inline std::size_t vk::Device::SamplingRoutineCache::Key::Hash::operator() (const Key& key) const noexcept
+{
+	auto hash = key.instruction;
+	hash = (hash * 31) ^ key.sampler;
+	hash = (hash * 31) ^ key.imageView;
+	return hash;
+}
+
 } // namespace vk
 
 #endif // VK_DEVICE_HPP_