1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
|
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
#ifndef CROSSLOADERALLOCATORHASH_H
#define CROSSLOADERALLOCATORHASH_H
#ifndef CROSSGEN_COMPILE
#include "gcheaphashtable.h"
class LoaderAllocator;
template <class TKey_, class TValue_>
class NoRemoveDefaultCrossLoaderAllocatorHashTraits
{
public:
typedef TKey_ TKey;
typedef TValue_ TValue;
static bool IsNull(const TValue &value) { return value == NULL; }
static TValue NullValue() { return NULL; }
#ifndef DACCESS_COMPILE
static void SetUsedEntries(TValue* pStartOfValuesData, DWORD entriesInArrayTotal, DWORD usedEntries);
static bool AddToValuesInHeapMemory(OBJECTREF *pKeyValueStore, const TKey& key, const TValue& value);
#endif //!DACCESS_COMPILE
static DWORD ComputeUsedEntries(OBJECTREF *pKeyValueStore, DWORD *pEntriesInArrayTotal);
template <class Visitor>
static bool VisitKeyValueStore(OBJECTREF *pLoaderAllocatorRef, OBJECTREF *pKeyValueStore, Visitor &visitor);
static TKey ReadKeyFromKeyValueStore(OBJECTREF *pKeyValueStore);
};
template <class TKey_, class TValue_>
class DefaultCrossLoaderAllocatorHashTraits : public NoRemoveDefaultCrossLoaderAllocatorHashTraits<TKey_, TValue_>
{
public:
typedef TKey_ TKey;
typedef TValue_ TValue;
#ifndef DACCESS_COMPILE
static void DeleteValueInHeapMemory(OBJECTREF keyValueStore, const TValue& value);
#endif //!DACCESS_COMPILE
};
struct GCHeapHashDependentHashTrackerHashTraits : public DefaultGCHeapHashTraits<true>
{
typedef LoaderAllocator* PtrTypeKey;
static INT32 Hash(PtrTypeKey *pValue);
static INT32 Hash(PTRARRAYREF arr, INT32 index);
static bool DoesEntryMatchKey(PTRARRAYREF arr, INT32 index, PtrTypeKey *pKey);
static bool IsDeleted(PTRARRAYREF arr, INT32 index, GCHEAPHASHOBJECTREF gcHeap);
};
typedef GCHeapHash<GCHeapHashDependentHashTrackerHashTraits> GCHeapHashDependentHashTrackerHash;
template<class TRAITS>
struct KeyToValuesGCHeapHashTraits : public DefaultGCHeapHashTraits<true>
{
template <class TKey>
static INT32 Hash(TKey *pValue);
static INT32 Hash(PTRARRAYREF arr, INT32 index);
template<class TKey>
static bool DoesEntryMatchKey(PTRARRAYREF arr, INT32 index, TKey *pKey);
};
// Hashtable of key to a list of values where the key may live in a different loader allocator
// than the value and this should not keep the loaderallocator of the value alive. The type of
// keys/values is defined via the TRAITS template argument, but must be non-gc pointers, and
// must be copyable without a copy constructor/require a destructor.
//
// This is managed via a series of different hashtables and data structures that are carefully
// engineered to be relatively memory efficient, yet still provide the ability to safely use
// the hashtable to hold relationships across LoaderAllocators which are not generally safe.
//
// In particular, given LoaderAllocator LA1 and LA2, where a reference to LA1 is not
// guaranteed to keep LA2 alive, this data structure can permit a pointer to an object which
// is defined as part of LA1 to be used as a key to find a pointer to an object that has the
// same lifetime as LA2.
//
// This data structure exposes Remove api's, but its primary use case is the combination of
// the Add and VisitValuesOfKey apis.
//
// To use Add, simply, call Add(TKey key, TValue value). This will add to the list of values
// associated with a key. The Add api should be called on a key's which are associated with
// the same LoaderAllocator as the CrossLoaderAllocatorHash.
//
// VisitValuesOfKey will visit all values that have the same key.
//
// IMPLEMENTATION DESIGN
// This data structure is a series of hashtables and lists.
//
// In general, this data structure builds a set of values associated with a key per
// LoaderAllocator. The lists per loader allocator are controlled via the TRAITS template. The
// TRAITS specify how the individual lists are handled, and do the copying in and out of the data
// structures. It is not expected that additional traits implementations will be needed for use,
// unless duplicate prevention is needed.
//
// BASIC STRUCTURE
//
// m_keyToDependentTrackersHash - Hashtable of key -> (list of values in primary loader allocator,
// hashtable of DependentTrackers)
//
// For each key in the table, there is at list of values in the primary loader allocator,
// and optionally there may be a hashtable of dependent trackers
//
// m_loaderAllocatorToDependentTrackerHash - Hashtable of LoaderAllocator to DependentTracker. Used to find
// dependent trackers for insertion into per key sets.
//
// The DependentTracker is an object (with a finalizer) which is associated with a specific
// LoaderAllocator, and uses a DependentHandle to hold onto a hashtable from Key to List of
// Values (for a specific LoaderAllocator). This dependent handle will keep that hashtable alive
// as long as the associated LoaderAllocator is live.
//
// The DependentTracker hashes (both the m_loaderAllocatorToDependentTrackerHash, and the per key hashes) are
// implemented via a hashtable which is "self-cleaning". In particular as the hashtable is
// walked for Add/Visit/Remove operations, if a DependentTracker is found which where the
// DependentHandle has detected that the LoaderAllocator has been freed, then the entry in
// the hashtable will set itself to the DELETED state. This cleaning operation will not occur
// eagerly, but it should prevent unbounded size growth as collectible LoaderAllocators are
// allocated and freed.
//
// Memory efficiency of this data structure.
// - This data structure is reasonably memory efficient. If many values share the same key
// then the memory efficiency per key trends toward 1.3333 * sizeof(Value). Otherwise basic
// cost per key/value pair (assuming they are pointer sized has an overhead of about 4
// pointers + key/value data size.)
template <class TRAITS>
class CrossLoaderAllocatorHash
{
private:
typedef typename TRAITS::TKey TKey;
typedef typename TRAITS::TValue TValue;
typedef GCHeapHash<KeyToValuesGCHeapHashTraits<TRAITS>> KeyToValuesGCHeapHash;
public:
#ifndef DACCESS_COMPILE
// Add an entry to the CrossLoaderAllocatorHash, the default implementation of does DefaultCrossLoaderAllocatorHashTraits will not check for duplicates.
void Add(TKey key, TValue value, LoaderAllocator *pLoaderAllocatorOfValue);
// Remove an entry to the CrossLoaderAllocatorHash, only removes one entry
void Remove(TKey key, TValue value, LoaderAllocator *pLoaderAllocatorOfValue);
// Remove all entries that can be looked up by key
void RemoveAll(TKey key);
#endif
// Using visitor walk all values associated with a given key. The visitor
// is expected to implement bool operator ()(OBJECTREF keepAlive, TKey key, TValue value).
// Return false from that function to stop visitation.
// This can be done simply by utilizing a lambda, or if a lambda cannot be used, a functor will do.
// The value of "value" in this case must not escape from the visitor object
// unless the keepAlive OBJECTREF is also kept alive
template <class Visitor>
bool VisitValuesOfKey(TKey key, Visitor &visitor);
// Visit all key/value pairs
template <class Visitor>
bool VisitAllKeyValuePairs(Visitor &visitor);
// Initialize this CrossLoaderAllocatorHash to be associated with a specific LoaderAllocator
// Must be called before any use of Add
void Init(LoaderAllocator *pAssociatedLoaderAllocator);
private:
#ifndef DACCESS_COMPILE
void EnsureManagedObjectsInitted();
LAHASHDEPENDENTHASHTRACKERREF GetDependentTrackerForLoaderAllocator(LoaderAllocator* pLoaderAllocator);
GCHEAPHASHOBJECTREF GetKeyToValueCrossLAHashForHashkeyToTrackers(LAHASHKEYTOTRACKERSREF hashKeyToTrackersUnsafe, LoaderAllocator* pValueLoaderAllocator);
#endif // !DACCESS_COMPILE
template <class Visitor>
static bool VisitKeyValueStore(OBJECTREF *pLoaderAllocatorRef, OBJECTREF *pKeyValueStore, Visitor &visitor);
template <class Visitor>
static bool VisitTracker(TKey key, LAHASHDEPENDENTHASHTRACKERREF trackerUnsafe, Visitor &visitor);
template <class Visitor>
static bool VisitTrackerAllEntries(LAHASHDEPENDENTHASHTRACKERREF trackerUnsafe, Visitor &visitor);
template <class Visitor>
static bool VisitKeyToTrackerAllEntries(OBJECTREF hashKeyEntryUnsafe, Visitor &visitor);
static void DeleteEntryTracker(TKey key, LAHASHDEPENDENTHASHTRACKERREF trackerUnsafe);
private:
LoaderAllocator *m_pLoaderAllocator = 0;
OBJECTHANDLE m_loaderAllocatorToDependentTrackerHash = 0;
OBJECTHANDLE m_keyToDependentTrackersHash = 0;
OBJECTHANDLE m_globalDependentTrackerRootHandle = 0;
};
class CrossLoaderAllocatorHashSetup
{
public:
inline static void EnsureTypesLoaded();
};
#endif // !CROSSGEN_COMPILE
#endif // CROSSLOADERALLOCATORHASH_H
|
