layers: Add canonical/unique ID to pipeline layout

Add unique ID's to pipeline layout needed for pipeline layout
compatibilty revamp in subsequent commit.  Refactor unique ID support
into common Dictionary implementation.

Change-Id: I0d864c8ef3b3406d6444aed4d73078d25d5eb26f

5 files changed, 163 insertions, 45 deletions

diff --git a/layers/core_validation.cpp b/layers/core_validation.cpp
index b2f11eef..171891b0 100644
--- a/layers/core_validation.cpp
+++ b/layers/core_validation.cpp
@@ -89,6 +89,36 @@ using mutex_t = std::mutex;
 using lock_guard_t = std::lock_guard<mutex_t>;
 using unique_lock_t = std::unique_lock<mutex_t>;
 
+// These functions are defined *outside* the core_validation namespace as their type
+// is also defined outside that namespace
+size_t PipelineLayoutCompatDef::hash() const {
+    hash_util::HashCombiner hc;
+    // The set number is integral to the CompatDef's distinctiveness
+    hc << set << push_constant_ranges.get();
+    const auto &layout_layout = *layout_id.get();
+    for (uint32_t i = 0; i <= set; i++) {
+        hc << layout_layout[i].get();
+    }
+    return hc.Value();
+}
+
+bool PipelineLayoutCompatDef::operator==(const PipelineLayoutCompatDef &other) const {
+    if ((set != other.set) || (push_constant_ranges != other.push_constant_ranges)) {
+        return false;
+    }
+
+    const auto &layout_layout = *layout_id.get();
+    assert(set < layout_layout.size());
+    const auto &other_ll = *other.layout_id.get();
+    assert(set < other_ll.size());
+    for (uint32_t i = 0; i <= set; i++) {
+        if (layout_layout[i] != other_ll[i]) {
+            return false;
+        }
+    }
+    return true;
+}
+
 namespace core_validation {
 
 using std::max;
@@ -5379,10 +5409,6 @@ static bool PreCallValiateCreatePipelineLayout(const layer_data *dev_data, const
     return skip;
 }
 
-// Note: std::equal_to is looking for operator == to be defined in the innermost namespace enclosing DescriptorSetLayoutDef
-//       (i.e. cvdescriptorset) or in the class, base, or containing classes, and does *not* look in :: for it.
-static std::unordered_map<PushConstantRanges, PushConstantRangesId, std::hash<PushConstantRanges>> push_constant_ranges_dict;
-
 // For repeatable sorting, not very useful for "memory in range" search
 struct PushConstantRangeCompare {
     bool operator()(const VkPushConstantRange *lhs, const VkPushConstantRange *rhs) const {
@@ -5397,12 +5423,13 @@ struct PushConstantRangeCompare {
         return lhs->offset < rhs->offset;
     }
 };
-PushConstantRangesId get_definition_id(const VkPipelineLayoutCreateInfo *info) {
+
+static PushConstantRangesDict push_constant_ranges_dict;
+
+PushConstantRangesId get_canonical_id(const VkPipelineLayoutCreateInfo *info) {
     if (!info->pPushConstantRanges) {
-        // Hand back the empty entry (creating as needed)... see below for syntax notes
-        PushConstantRangesId empty = std::make_shared<PushConstantRanges>();
-        auto insert_pair = push_constant_ranges_dict.insert({*empty, empty});
-        return insert_pair.first->second;
+        // Hand back the empty entry (creating as needed)...
+        return push_constant_ranges_dict.look_up(PushConstantRanges());
     }
 
     // Sort the input ranges to ensure equivalent ranges map to the same id
@@ -5410,19 +5437,23 @@ PushConstantRangesId get_definition_id(const VkPipelineLayoutCreateInfo *info) {
     for (uint32_t i = 0; i < info->pushConstantRangeCount; i++) {
         sorted.insert(info->pPushConstantRanges + i);
     }
+
     PushConstantRanges ranges(sorted.size());
     for (const auto range : sorted) {
         ranges.emplace_back(*range);
     }
-    PushConstantRangesId from_input = std::make_shared<PushConstantRanges>(std::move(ranges));
+    return push_constant_ranges_dict.look_up(std::move(ranges));
+}
+
+// Dictionary of canoncial form of the pipeline set layout of descriptor set layouts
+static DescriptorSetLayoutLayoutDict layout_layout_dict;
 
-    // Insert takes care of the "unique" id part by rejecting the insert if a key matching ranges exists, but returning us
-    // the entry with the extant shared_pointer(id->def) instead.
-    auto insert_pair = push_constant_ranges_dict.insert({*from_input, from_input});
+// Dictionary of canonical form of the "compatible for set" records
+static PipelineLayoutCompatDict pipeline_layout_compat_dict;
 
-    // Return the value by dereferencing the Iterator from the <It, bool> pair returned by insert, and taking the value from the
-    // <key, value> pair of the Iterator
-    return insert_pair.first->second;
+static PipelineLayoutCompatId get_canonical_id(const uint32_t set_index, const PushConstantRangesId pcr_id,
+                                               const DescriptorSetLayoutLayoutId ll_id) {
+    return pipeline_layout_compat_dict.look_up(PipelineLayoutCompatDef(set_index, pcr_id, ll_id));
 }
 
 static void PostCallRecordCreatePipelineLayout(layer_data *dev_data, const VkPipelineLayoutCreateInfo *pCreateInfo,
@@ -5432,10 +5463,22 @@ static void PostCallRecordCreatePipelineLayout(layer_data *dev_data, const VkPip
     PIPELINE_LAYOUT_NODE &plNode = dev_data->pipelineLayoutMap[*pPipelineLayout];
     plNode.layout = *pPipelineLayout;
     plNode.set_layouts.resize(pCreateInfo->setLayoutCount);
+    DescriptorSetLayoutLayoutDef layout_layout(pCreateInfo->setLayoutCount);
     for (uint32_t i = 0; i < pCreateInfo->setLayoutCount; ++i) {
         plNode.set_layouts[i] = GetDescriptorSetLayout(dev_data, pCreateInfo->pSetLayouts[i]);
+        layout_layout[i] = plNode.set_layouts[i]->get_layout_id();
     }
-    plNode.push_constant_ranges = get_definition_id(pCreateInfo);
+
+    // Get canonical form IDs for the "compatible for set" contents
+    plNode.push_constant_ranges = get_canonical_id(pCreateInfo);
+    auto ll_id = layout_layout_dict.look_up(layout_layout);
+    plNode.compat_for_set.reserve(pCreateInfo->setLayoutCount);
+
+    // Create table of "compatible for set N" cannonical forms for trivial accept validation
+    for (uint32_t i = 0; i < pCreateInfo->setLayoutCount; ++i) {
+        plNode.compat_for_set.emplace_back(get_canonical_id(i, plNode.push_constant_ranges, ll_id));
+    }
+
     // Implicit unlock
 };
 
diff --git a/layers/core_validation_types.h b/layers/core_validation_types.h
index 67392d41..75e3b736 100644
--- a/layers/core_validation_types.h
+++ b/layers/core_validation_types.h
@@ -40,8 +40,9 @@
 #include <memory>
 #include <list>
 
-// Fwd declarations
+// Fwd declarations -- including descriptor_set.h creates an ugly include loop
 namespace cvdescriptorset {
+class DescriptorSetLayoutDef;
 class DescriptorSetLayout;
 class DescriptorSet;
 }  // namespace cvdescriptorset
@@ -543,21 +544,51 @@ struct hash<ImageSubresourcePair> {
 };
 }  // namespace std
 
-// The id defines a unique ID based on the contents of a PushConstantRanges set;
-using PushConstantRangesId = std::shared_ptr<PushConstantRanges>;
+// Canonical dictionary for PushConstantRanges
+using PushConstantRangesDict = hash_util::Dictionary<PushConstantRanges>;
+using PushConstantRangesId = PushConstantRangesDict::Id;
+
+// Canonical dictionary for the pipeline layout's layout of descriptorsetlayouts
+using DescriptorSetLayoutDef = cvdescriptorset::DescriptorSetLayoutDef;
+using DescriptorSetLayoutId = std::shared_ptr<const DescriptorSetLayoutDef>;
+using DescriptorSetLayoutLayoutDef = std::vector<DescriptorSetLayoutId>;
+using DescriptorSetLayoutLayoutDict =
+    hash_util::Dictionary<DescriptorSetLayoutLayoutDef, hash_util::IsOrderedContainer<DescriptorSetLayoutLayoutDef>>;
+using DescriptorSetLayoutLayoutId = DescriptorSetLayoutLayoutDict::Id;
+
+// Defines/stores a compatibility defintion for set N
+// The "layout layout" must store at least set+1 entries, but only the first set+1 are considered for hash and equality testing
+// Note: the "cannonical" data are referenced by Id, not including handle or device specific state
+// Note: hash and equality only consider layout_id entries [0, set] for determining uniqueness
+struct PipelineLayoutCompatDef {
+    uint32_t set;
+    PushConstantRangesId push_constant_ranges;
+    using LayoutLayout = DescriptorSetLayoutLayoutId;
+    LayoutLayout layout_id;
+    PipelineLayoutCompatDef(const uint32_t set_index, const PushConstantRangesId pcr_id, const LayoutLayout ll_id)
+        : set(set_index), push_constant_ranges(pcr_id), layout_id(ll_id) {}
+    size_t hash() const;
+    bool operator==(const PipelineLayoutCompatDef &other) const;
+};
+
+// Canonical dictionary for PipelineLayoutCompat records
+using PipelineLayoutCompatDict = hash_util::Dictionary<PipelineLayoutCompatDef, hash_util::HasHashMember<PipelineLayoutCompatDef>>;
+using PipelineLayoutCompatId = PipelineLayoutCompatDict::Id;
 
 // Store layouts and pushconstants for PipelineLayout
 struct PIPELINE_LAYOUT_NODE {
     VkPipelineLayout layout;
     std::vector<std::shared_ptr<cvdescriptorset::DescriptorSetLayout const>> set_layouts;
     PushConstantRangesId push_constant_ranges;
+    std::vector<PipelineLayoutCompatId> compat_for_set;
 
-    PIPELINE_LAYOUT_NODE() : layout(VK_NULL_HANDLE), set_layouts{}, push_constant_ranges{} {}
+    PIPELINE_LAYOUT_NODE() : layout(VK_NULL_HANDLE), set_layouts{}, push_constant_ranges{}, compat_for_set{} {}
 
     void reset() {
         layout = VK_NULL_HANDLE;
         set_layouts.clear();
         push_constant_ranges.reset();
+        compat_for_set.clear();
     }
 };
 
diff --git a/layers/descriptor_sets.cpp b/layers/descriptor_sets.cpp
index 9f4d3a42..928e4095 100644
--- a/layers/descriptor_sets.cpp
+++ b/layers/descriptor_sets.cpp
@@ -40,28 +40,13 @@ struct BindingNumCmp {
 using DescriptorSetLayoutDef = cvdescriptorset::DescriptorSetLayoutDef;
 using DescriptorSetLayoutId = cvdescriptorset::DescriptorSetLayoutId;
 
-namespace std {
-template <>
-struct hash<DescriptorSetLayoutDef> : public hash_util::HasHashMember<DescriptorSetLayoutDef> {};
-}  // namespace std
+// Canonical dictionary of DescriptorSetLayoutDef (without any handle/device specific information)
+cvdescriptorset::DescriptorSetLayoutDict descriptor_set_layout_dict;
 
-// Note: std::equal_to is looking for operator == to be defined in the innermost namespace enclosing DescriptorSetLayoutDef
-//       (i.e. cvdescriptorset) or in the class, base, or containing classes, and does *not* look in :: for it.
-static std::unordered_map<DescriptorSetLayoutDef, DescriptorSetLayoutId, std::hash<DescriptorSetLayoutDef>,
-                          std::equal_to<DescriptorSetLayoutDef>>
-    descriptor_set_layout_dict;
-
-DescriptorSetLayoutId get_definition_id(const VkDescriptorSetLayoutCreateInfo *p_create_info) {
-    DescriptorSetLayoutId from_input = std::make_shared<DescriptorSetLayoutDef>(p_create_info);
-
-    // Insert takes care of the "unique" id part by rejecting the insert if a key matching the DSL def exists, but returning us
-    // the entry with the extant shared_pointer(id->def) instead.
-    auto insert_pair = descriptor_set_layout_dict.insert({*from_input, from_input});
-
-    // This *awful* syntax takes the Iterator from the <It, bool> pair returned by insert, and extracts the value from the
-    // <key, value> pair of the Iterator
-    return insert_pair.first->second;
+DescriptorSetLayoutId get_canonical_id(const VkDescriptorSetLayoutCreateInfo *p_create_info) {
+    return descriptor_set_layout_dict.look_up(DescriptorSetLayoutDef(p_create_info));
 }
+
 // Construct DescriptorSetLayout instance from given create info
 // Proactively reserve and resize as possible, as the reallocation was visible in profiling
 cvdescriptorset::DescriptorSetLayoutDef::DescriptorSetLayoutDef(const VkDescriptorSetLayoutCreateInfo *p_create_info)
@@ -338,7 +323,7 @@ bool cvdescriptorset::DescriptorSetLayoutDef::VerifyUpdateConsistency(uint32_t c
 // handle invariant portion
 cvdescriptorset::DescriptorSetLayout::DescriptorSetLayout(const VkDescriptorSetLayoutCreateInfo *p_create_info,
                                                           const VkDescriptorSetLayout layout)
-    : layout_(layout), layout_destroyed_(false), layout_id_(get_definition_id(p_create_info)) {}
+    : layout_(layout), layout_destroyed_(false), layout_id_(get_canonical_id(p_create_info)) {}
 
 // Validate descriptor set layout create info
 bool cvdescriptorset::DescriptorSetLayout::ValidateCreateInfo(const debug_report_data *report_data,
diff --git a/layers/descriptor_sets.h b/layers/descriptor_sets.h
index aa11c524..866de8c9 100644
--- a/layers/descriptor_sets.h
+++ b/layers/descriptor_sets.h
@@ -53,11 +53,17 @@ struct IndexRange {
 typedef std::map<uint32_t, descriptor_req> BindingReqMap;
 
 /*
- * DescriptorSetLayout class
+ * DescriptorSetLayoutDef/DescriptorSetLayout classes
  *
- * Overview - This class encapsulates the Vulkan VkDescriptorSetLayout data (layout).
+ * Overview - These two classes encapsulate the Vulkan VkDescriptorSetLayout data (layout).
  *   A layout consists of some number of bindings, each of which has a binding#, a
  *   type, descriptor count, stage flags, and pImmutableSamplers.
+
+ *   The DescriptorSetLayoutDef represents a canonicalization of the input data and contains
+ *   neither per handle or per device state.  It is possible for different handles on
+ *   different devices to share a common def.  This is used and useful for quick compatibiltiy
+ *   validation.  The DescriptorSetLayout refers to a DescriptorSetLayoutDef and contains
+ *   all per handle state.
  *
  * Index vs Binding - A layout is created with an array of VkDescriptorSetLayoutBinding
  *  where each array index will have a corresponding binding# that is defined in that struct.
@@ -178,7 +184,9 @@ static bool operator==(const DescriptorSetLayoutDef &lhs, const DescriptorSetLay
     return (lhs.GetCreateFlags() == rhs.GetCreateFlags()) && (lhs.GetBindings() == rhs.GetBindings());
 }
 
-using DescriptorSetLayoutId = std::shared_ptr<DescriptorSetLayoutDef>;
+// Canonical dictionary of DSL definitions -- independent of device or handle
+using DescriptorSetLayoutDict = hash_util::Dictionary<DescriptorSetLayoutDef, hash_util::HasHashMember<DescriptorSetLayoutDef>>;
+using DescriptorSetLayoutId = DescriptorSetLayoutDict::Id;
 
 class DescriptorSetLayout {
    public:
@@ -195,6 +203,7 @@ class DescriptorSetLayout {
     bool IsDestroyed() const { return layout_destroyed_; }
     void MarkDestroyed() { layout_destroyed_ = true; }
     const DescriptorSetLayoutDef *get_layout_def() const { return layout_id_.get(); }
+    DescriptorSetLayoutId get_layout_id() const { return layout_id_; }
     uint32_t GetTotalDescriptorCount() const { return layout_id_->GetTotalDescriptorCount(); };
     uint32_t GetDynamicDescriptorCount() const { return layout_id_->GetDynamicDescriptorCount(); };
     uint32_t GetBindingCount() const { return layout_id_->GetBindingCount(); };
diff --git a/layers/hash_util.h b/layers/hash_util.h
index e5f995a1..ea31231f 100644
--- a/layers/hash_util.h
+++ b/layers/hash_util.h
@@ -24,7 +24,10 @@
 #include <cstdint>
 #include <functional>
 #include <limits>
+#include <memory>
+#include <mutex>
 #include <type_traits>
+#include <unordered_set>
 #include <vector>
 
 // Hash and equality utilities for supporting hashing containers (e.g. unordered_set, unordered_map)
@@ -109,6 +112,53 @@ struct IsOrderedContainer {
     size_t operator()(const T &value) const { return HashCombiner().Combine(value.cbegin(), value.cend()).Value(); }
 };
 
+// The dictionary provides a way of referencing canonical/reference
+// data by id, such that the id's are invariant with dictionary
+// resize/insert and that no entries point to identical data.  This
+// approach uses the address of the unique data and as the unique
+//  ID  for a give value of T.
+//
+// Note: This ID is unique for a given application execution, neither
+//       globally unique, invariant, nor repeatable from execution to
+//       execution.
+//
+// The entries of the dictionary are shared_pointers (the contents of
+// which are invariant with resize/insert), with the hash and equality
+// template arguments wrapped in a shared pointer dereferencing
+// function object
+template <typename T, typename Hasher = std::hash<T>, typename KeyEqual = std::equal_to<T>>
+class Dictionary {
+   public:
+    using Def = T;
+    using Id = std::shared_ptr<const Def>;
+
+    // Find the unique entry match the provided value, adding if needed
+    // TODO: segregate lookup from insert, using reader/write locks to reduce contention -- if needed
+    template <typename U = T>
+    Id look_up(U &&value) {
+        // We create an Id from the value, which will either be retained by dict (if new) or deleted on return (if extant)
+        Id from_input = std::make_shared<T>(std::forward<U>(value));
+
+        // Insert takes care of the "unique" id part by rejecting the insert if a key matching by_value exists, but returning us
+        // the Id of the extant shared_pointer(id->def) instead.
+        // return the value of the Iterator from the <Iterator, bool> pair returned by insert
+        Guard g(lock);  // Dict isn't thread safe, and use is presumed to be multi-threaded
+        return *dict.insert(from_input).first;
+    }
+
+   private:
+    struct HashKeyValue {
+        size_t operator()(const Id &value) const { return Hasher()(*value); }
+    };
+    struct KeyValueEqual {
+        bool operator()(const Id &lhs, const Id &rhs) const { return KeyEqual()(*lhs, *rhs); }
+    };
+    using Dict = std::unordered_set<Id, HashKeyValue, KeyValueEqual>;
+    using Lock = std::mutex;
+    using Guard = std::lock_guard<Lock>;
+    Lock lock;
+    Dict dict;
+};
 }  // namespace hash_util
 
 #endif  // HASH_UTILS_H_