Cuckoo metadata (#24498)

* Basic infra for cuckoo filter of attributes
- Implement cuckoo filter lookup logic
- Implement new ready to run section
 - Add dumper to R2RDump
 - Parse section on load into data structure
 - Implement function to query filter
- Add concept of enum of well known attributes
  - So that attribute name hashes themselves may be cached
* Wrap all even vaguely perf critical uses of attribute by name parsing with use of R2R data
* Update emmintrin.h in the PAL header to contain the needed SSE2 intrinsics for the feature
- Disable the presence table for non Corelib cases. Current performance data does not warrant the size increase in other generated binaries

4 files changed, 69 insertions, 0 deletions

diff --git a/src/tools/r2rdump/NativeHashtable.cs b/src/tools/r2rdump/NativeHashtable.cs
index 830805eee5..44e7b3fd4f 100644
--- a/src/tools/r2rdump/NativeHashtable.cs
+++ b/src/tools/r2rdump/NativeHashtable.cs
@@ -238,4 +238,61 @@ namespace R2RDump
             return new AllEntriesEnumerator(this);
         }
     }
+
+    /// <summary>
+    /// based on <a href="https://github.com/dotnet/coreclr/blob/master/src/vm/nativeformatreader.h">NativeFormat::NativeHashtable</a>
+    /// </summary>
+    struct NativeCuckooFilter
+    {
+        private byte[] _image;
+        private int _filterStartOffset;
+        private int _filterEndOffset;
+
+        public NativeCuckooFilter(byte[] image, int filterStartOffset, int filterEndOffset)
+        {
+            _image = image;
+            _filterStartOffset = filterStartOffset;
+            _filterEndOffset = filterEndOffset;
+
+            if (((_filterStartOffset & 0xF) != 0) || ((_filterEndOffset & 0xF) != 0))
+            {
+                // Native cuckoo filters must be aligned at 16byte boundaries within the PE file
+                throw new System.BadImageFormatException();
+            }
+        }
+
+        private IEnumerable<ushort[]> GetBuckets()
+        {
+            int offset = _filterStartOffset;
+            while (offset < _filterEndOffset)
+            {
+                ushort[] bucket = new ushort[8];
+                for (int i = 0; i < bucket.Length; i++)
+                {
+                    bucket[i] = NativeReader.ReadUInt16(_image, ref offset);
+                }
+                yield return bucket;
+            }
+        }
+
+        public override string ToString()
+        {
+            StringBuilder sb = new StringBuilder();
+
+            sb.AppendLine($"NativeCuckooFilter Size: {(_filterEndOffset - _filterStartOffset) / 16}");
+            int bucket = 0;
+            foreach (ushort [] bucketContents in GetBuckets())
+            {
+                sb.Append($"Bucket: {bucket} [");
+                for (int i = 0; i < 8; i++)
+                {
+                    sb.Append($"{bucketContents[i],4:X} ");
+                }
+                sb.AppendLine("]");
+                bucket++;
+            }
+
+            return sb.ToString();
+        }
+    }
 }
diff --git a/src/tools/r2rdump/R2RSection.cs b/src/tools/r2rdump/R2RSection.cs
index 3ba922b609..0eca7e9a51 100644
--- a/src/tools/r2rdump/R2RSection.cs
+++ b/src/tools/r2rdump/R2RSection.cs
@@ -29,6 +29,7 @@ namespace R2RDump
             READYTORUN_SECTION_INLINING_INFO = 110,
             READYTORUN_SECTION_PROFILEDATA_INFO = 111,
             READYTORUN_SECTION_MANIFEST_METADATA = 112, // Added in v2.3
+            READYTORUN_SECTION_ATTRIBUTEPRESENCE = 113, // Added in V3.1
         }
 
         /// <summary>
diff --git a/src/tools/r2rdump/README.md b/src/tools/r2rdump/README.md
index 0d7bdb9ad6..ee16e40573 100644
--- a/src/tools/r2rdump/README.md
+++ b/src/tools/r2rdump/README.md
@@ -81,6 +81,10 @@ A [NativeArray](NativeArray.cs) used for finding the index of the entrypoint Run
 
 A [NativeHashtable](NativeHashtable.cs) mapping type hashcodes of types defined in the program to the rowIds. The hashcode is calculated with [ComputeNameHashCode](../../vm/typehashingalgorithms.h)(namespace) ^ [ComputeNameHashCode](../../vm/typehashingalgorithms.h)(name)
 
+### READYTORUN_SECTION_ATTRIBUTEPRESENCE
+
+A [NativeCuckooFilter](NativeHashtable.cs) to discover which tokens have which "System.Runtime." prefixed attributes. The System.Runtime.CompilerServices.NullableAttribute is not used in this calculation. The filter is composed of a name hash of the type name using [ComputeNameHashCode](../../vm/typehashingalgorithms.h)(namespace + name) hash combined with a hash of each token that produced it. In addition the upper 16 bits is used as the fingerprint in the filter. 
+
 ### READYTORUN_SECTION_INSTANCE_METHOD_ENTRYPOINTS
 
 A [NativeHashtable](NativeHashtable.cs) mapping type hashcodes of generic instances to the (methodFlags, methodRowId, list of types, runtimeFunctionId). Each type in the list of types corresponds to a generic type in the method.
diff --git a/src/tools/r2rdump/TextDumper.cs b/src/tools/r2rdump/TextDumper.cs
index db4c5f3eeb..b1528df37a 100644
--- a/src/tools/r2rdump/TextDumper.cs
+++ b/src/tools/r2rdump/TextDumper.cs
@@ -374,6 +374,13 @@ namespace R2RDump
                         _writer.WriteLine($"[ID 0x{manifestAsmIndex + assemblyRefCount + 2:X2}]: {_r2r.ManifestReferenceAssemblies[manifestAsmIndex]}");
                     }
                     break;
+                case R2RSection.SectionType.READYTORUN_SECTION_ATTRIBUTEPRESENCE:
+                    int attributesStartOffset = _r2r.GetOffset(section.RelativeVirtualAddress);
+                    int attributesEndOffset = attributesStartOffset + section.Size;
+                    NativeCuckooFilter attributes = new NativeCuckooFilter(_r2r.Image, attributesStartOffset, attributesEndOffset);
+                    _writer.WriteLine("Attribute presence filter");
+                    _writer.WriteLine(attributes.ToString());
+                    break;
             }
         }