-
Notifications
You must be signed in to change notification settings - Fork 392
/
MemoryPoolSplitAddressOrderedListBase.hpp
403 lines (346 loc) · 12.8 KB
/
MemoryPoolSplitAddressOrderedListBase.hpp
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
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
/*******************************************************************************
* Copyright (c) 1991, 2019 IBM Corp. and others
*
* This program and the accompanying materials are made available under
* the terms of the Eclipse Public License 2.0 which accompanies this
* distribution and is available at https://www.eclipse.org/legal/epl-2.0/
* or the Apache License, Version 2.0 which accompanies this distribution and
* is available at https://www.apache.org/licenses/LICENSE-2.0.
*
* This Source Code may also be made available under the following
* Secondary Licenses when the conditions for such availability set
* forth in the Eclipse Public License, v. 2.0 are satisfied: GNU
* General Public License, version 2 with the GNU Classpath
* Exception [1] and GNU General Public License, version 2 with the
* OpenJDK Assembly Exception [2].
*
* [1] https://www.gnu.org/software/classpath/license.html
* [2] http://openjdk.java.net/legal/assembly-exception.html
*
* SPDX-License-Identifier: EPL-2.0 OR Apache-2.0 OR GPL-2.0 WITH Classpath-exception-2.0 OR LicenseRef-GPL-2.0 WITH Assembly-exception
*******************************************************************************/
/**
* @file
* @ingroup GC_Base_Core
*/
#if !defined(MEMORYPOOLSPLITADDRESSORDEREDLISTBASE_HPP_)
#define MEMORYPOOLSPLITADDRESSORDEREDLISTBASE_HPP_
#include "omrcfg.h"
#include "modronopt.h"
#include "HeapLinkedFreeHeader.hpp"
#include "LightweightNonReentrantLock.hpp"
#include "MemoryPoolAddressOrderedListBase.hpp"
#include "EnvironmentBase.hpp"
class MM_AllocateDescription;
class J9ModronFreeList {
public:
MM_LightweightNonReentrantLock _lock;
MM_HeapLinkedFreeHeader* _freeList;
uintptr_t _timesLocked;
uintptr_t _freeSize;
uintptr_t _freeCount;
/* Hint support */
struct J9ModronAllocateHint* _hintActive;
struct J9ModronAllocateHint* _hintInactive;
struct J9ModronAllocateHint _hintStorage[HINT_ELEMENT_COUNT];
uintptr_t _hintLru;
bool initialize(MM_EnvironmentBase* env);
void tearDown();
void clearHints();
void reset();
MMINLINE void addHint(MM_HeapLinkedFreeHeader* freeEntry, uintptr_t lookupSize)
{
/* Travel the list removing any hints that this new hint will override */
J9ModronAllocateHint* previousActiveHint = NULL;
J9ModronAllocateHint* currentActiveHint = _hintActive;
J9ModronAllocateHint* nextActiveHint = NULL;
while (currentActiveHint) {
/* Check what address range the free header to be added lies in (below, equal, above) */
if (freeEntry < currentActiveHint->heapFreeHeader) {
if (lookupSize >= currentActiveHint->size) {
/* remove this hint */
goto removeHint;
}
} else {
if (freeEntry == currentActiveHint->heapFreeHeader) {
if (lookupSize < currentActiveHint->size) {
/* remove this hint */
goto removeHint;
} else {
/* The hint to be added is redundant */
return;
}
} else {
/* freeEntry > currentActiveHint->heapFreeHeader <--- implied */
if (lookupSize <= currentActiveHint->size) {
/* remove this hint */
goto removeHint;
}
}
}
/* Do nothing to this hint - move to the next one */
previousActiveHint = currentActiveHint;
currentActiveHint = currentActiveHint->next;
continue;
removeHint:
/* Remove the currentActiveHint */
nextActiveHint = currentActiveHint->next;
if (previousActiveHint) {
previousActiveHint->next = nextActiveHint;
} else {
_hintActive = nextActiveHint;
}
currentActiveHint->next = _hintInactive;
_hintInactive = currentActiveHint;
currentActiveHint = nextActiveHint;
}
/* Get a hint from the list */
J9ModronAllocateHint* hint;
if (_hintInactive) {
/* Consume the hint from the inactive list */
hint = _hintInactive;
_hintInactive = hint->next;
/* Place new hint in active list */
hint->next = _hintActive;
_hintActive = hint;
} else {
J9ModronAllocateHint* currentHint;
/* Find the smallest LRU value and recycle the hint */
hint = _hintActive;
currentHint = hint->next;
while (currentHint) {
if (hint->lru > currentHint->lru) {
hint = currentHint;
}
currentHint = currentHint->next;
}
}
/* Update the global and local LRU */
hint->lru = _hintLru++;
/* Initialize the hint info */
hint->size = lookupSize;
hint->heapFreeHeader = freeEntry;
}
MMINLINE J9ModronAllocateHint* findHint(uintptr_t lookupSize)
{
J9ModronAllocateHint* hint = NULL;
J9ModronAllocateHint* candidateHint = _hintActive;
J9ModronAllocateHint* previousHint = NULL;
/* Be sure to remove stale hints as we search the list (stale hints are addresses < the heap free head) */
while (candidateHint) {
if (!_freeList || (candidateHint->heapFreeHeader < _freeList)) {
/* Hint is stale - remove */
J9ModronAllocateHint* nextHint;
if (previousHint) {
previousHint->next = candidateHint->next;
} else {
_hintActive = candidateHint->next;
}
nextHint = candidateHint->next;
candidateHint->next = _hintInactive;
_hintInactive = candidateHint;
candidateHint = nextHint;
} else {
if (candidateHint->size < lookupSize) {
if (hint) {
if (candidateHint->size > hint->size) {
hint = candidateHint;
}
} else {
hint = candidateHint;
}
}
previousHint = candidateHint;
candidateHint = candidateHint->next;
}
}
if (hint) {
/* Update the global and local LRU */
hint->lru = _hintLru++;
}
return hint;
}
MMINLINE void removeHint(MM_HeapLinkedFreeHeader* freeEntry)
{
J9ModronAllocateHint* hint = _hintActive;
J9ModronAllocateHint* previousHint = NULL;
J9ModronAllocateHint* nextHint = NULL;
while (hint) {
if (hint->heapFreeHeader == freeEntry) {
nextHint = hint->next;
/* Add the hint to the free list */
hint->next = _hintInactive;
_hintInactive = hint;
/* Glue the previous hint to the next hint */
if (previousHint) {
previousHint->next = nextHint;
} else {
/* no previous hint - must be the head */
_hintActive = nextHint;
}
hint = nextHint;
} else {
/* Move to the next hint */
previousHint = hint;
hint = hint->next;
}
}
}
MMINLINE void updateHint(MM_HeapLinkedFreeHeader* oldFreeEntry, MM_HeapLinkedFreeHeader* newFreeEntry)
{
J9ModronAllocateHint* hint = _hintActive;
bool found = false;
while (hint) {
if (hint->heapFreeHeader == oldFreeEntry) {
/*
* Should be no duplicates in hints
* check and assert if there is more then one
*/
Assert_MM_true(!found);
hint->heapFreeHeader = newFreeEntry;
found = true;
} else {
/* Move to the next hint */
hint = hint->next;
}
}
}
J9ModronFreeList()
: _freeList(NULL)
, _timesLocked(0)
, _freeSize(0)
, _freeCount(0)
, _hintActive(NULL)
, _hintInactive(NULL)
, _hintLru(0)
{
}
};
/**
* @todo Provide class documentation
* @ingroup GC_Base
*/
class MM_MemoryPoolSplitAddressOrderedListBase : public MM_MemoryPoolAddressOrderedListBase {
/*
* Data members
*/
private:
protected:
/* Basic free list support */
uintptr_t _heapFreeListCount;
uintptr_t _heapFreeListCountExtended;
uintptr_t* _currentThreadFreeList;
J9ModronFreeList* _heapFreeLists;
MM_LargeObjectAllocateStats* _largeObjectAllocateStatsForFreeList; /**< Approximate allocation profile for large objects. An array of stat structs for each free list */
MM_LargeObjectAllocateStats* _largeObjectCollectorAllocateStatsForFreeList; /**< Same as _largeObjectAllocateStatsForFreeList except specifically for collector allocates */
public:
/*
* Function members
*/
private:
protected:
virtual void *internalAllocate(MM_EnvironmentBase *env, uintptr_t sizeInBytesRequired, bool lockingRequired, MM_LargeObjectAllocateStats *largeObjectAllocateStats) = 0;
virtual bool internalAllocateTLH(MM_EnvironmentBase *env, uintptr_t maximumSizeInBytesRequired, void * &addrBase, void * &addrTop, bool lockingRequired, MM_LargeObjectAllocateStats *largeObjectAllocateStats) = 0;
bool recycleHeapChunkForFreeList(MM_EnvironmentBase* env, void* addrBase, void* addrTop, MM_HeapLinkedFreeHeader* previousFreeEntry, MM_HeapLinkedFreeHeader* nextFreeEntry, uintptr_t curFreeList);
MMINLINE uintptr_t findGoodStartFreeList()
{
uintptr_t index = 0;
uintptr_t timesLocked = UDATA_MAX;
for (uintptr_t i = 0; i < _heapFreeListCount; ++i) {
if ((NULL != _heapFreeLists[i]._freeList) && (_heapFreeLists[i]._timesLocked < timesLocked)) {
index = i;
timesLocked = _heapFreeLists[i]._timesLocked;
}
}
return index;
}
/**
* set Next of the freeEntry with new freeEntry pointer
*
* @param[in] freelist
* @param[in] freeEntry if freeEntry is NULL, set head of freelist with new freeEntry pointer
* @param[in] next the new freeEntry pointer, if it is NULL, reset Next of freeEntry
*/
MMINLINE void setNextForFreeEntryInFreeList(J9ModronFreeList* freelist, MM_HeapLinkedFreeHeader* freeEntry, MM_HeapLinkedFreeHeader* next)
{
bool const compressed = compressObjectReferences();
if (NULL == freeEntry) {
freelist->_freeList = next;
} else {
freeEntry->setNext(next, compressed);
}
}
bool printFreeListValidity(MM_EnvironmentBase* env);
public:
virtual void* allocateObject(MM_EnvironmentBase* env, MM_AllocateDescription* allocDescription);
virtual void* allocateTLH(MM_EnvironmentBase* env, MM_AllocateDescription* allocDescription, uintptr_t maximumSizeInBytesRequired, void*& addrBase, void*& addrTop);
virtual void* collectorAllocate(MM_EnvironmentBase* env, MM_AllocateDescription* allocDescription, bool lockingRequired);
virtual void* collectorAllocateTLH(MM_EnvironmentBase* env, MM_AllocateDescription* allocDescription, uintptr_t maximumSizeInBytesRequired, void*& addrBase, void*& addrTop, bool lockingRequired);
virtual void lock(MM_EnvironmentBase* env);
virtual void unlock(MM_EnvironmentBase* env);
virtual bool initialize(MM_EnvironmentBase* env);
virtual void tearDown(MM_EnvironmentBase* env);
virtual void reset(Cause cause = any);
virtual MM_HeapLinkedFreeHeader* rebuildFreeListInRegion(MM_EnvironmentBase* env, MM_HeapRegionDescriptor* region, MM_HeapLinkedFreeHeader* previousFreeEntry);
#if defined(DEBUG)
virtual bool isValidListOrdering();
#endif
virtual void* findAddressAfterFreeSize(MM_EnvironmentBase* env, uintptr_t sizeRequired, uintptr_t minimumSize);
virtual void* findFreeEntryEndingAtAddr(MM_EnvironmentBase* env, void* addr);
virtual uintptr_t getAvailableContractionSizeForRangeEndingAt(MM_EnvironmentBase* env, MM_AllocateDescription* allocDescription, void* lowAddr, void* highAddr);
virtual void* findFreeEntryTopStartingAtAddr(MM_EnvironmentBase* env, void* addr);
virtual void* getFirstFreeStartingAddr(MM_EnvironmentBase* env);
void* getFirstFreeStartingAddr(MM_EnvironmentBase* env, uintptr_t* currentFreeListReturn);
virtual void* getNextFreeStartingAddr(MM_EnvironmentBase* env, void* currentFree);
void* getNextFreeStartingAddr(MM_EnvironmentBase* env, void* currentFree, uintptr_t* currentFreeListIndex);
virtual void moveHeap(MM_EnvironmentBase* env, void* srcBase, void* srcTop, void* dstBase);
/**< Reset current (as opposed to average) large object allocate stats */
virtual void resetLargeObjectAllocateStats();
/**
* Merge the free entry stats from free lists.
*/
virtual void mergeFreeEntryAllocateStats();
/**
* Merge the tlh allocation distribution stats from free lists.
*/
virtual void mergeTlhAllocateStats();
/**
* Merge the current LargeObject allocation distribution stats from free lists.
*/
virtual void mergeLargeObjectAllocateStats();
virtual void appendCollectorLargeAllocateStats();
virtual void printCurrentFreeList(MM_EnvironmentBase* env, const char* area);
/**
* Recalculate the memory pool statistics by actually examining the contents of the pool.
*/
virtual void recalculateMemoryPoolStatistics(MM_EnvironmentBase* env);
virtual uintptr_t getActualFreeMemorySize();
virtual uintptr_t getActualFreeEntryCount();
/**
* Create a MemoryPoolAddressOrderedList object.
*/
MM_MemoryPoolSplitAddressOrderedListBase(MM_EnvironmentBase* env, uintptr_t minimumFreeEntrySize, uintptr_t splitAmount)
: MM_MemoryPoolAddressOrderedListBase(env, minimumFreeEntrySize)
, _heapFreeListCount(splitAmount)
, _heapFreeListCountExtended(splitAmount)
, _currentThreadFreeList(0)
, _heapFreeLists(NULL)
, _largeObjectAllocateStatsForFreeList(NULL)
, _largeObjectCollectorAllocateStatsForFreeList(NULL)
{
}
MM_MemoryPoolSplitAddressOrderedListBase(MM_EnvironmentBase* env, uintptr_t minimumFreeEntrySize, uintptr_t splitAmount, const char* name)
: MM_MemoryPoolAddressOrderedListBase(env, minimumFreeEntrySize, name)
, _heapFreeListCount(splitAmount)
, _heapFreeListCountExtended(splitAmount)
, _currentThreadFreeList(0)
, _heapFreeLists(NULL)
, _largeObjectAllocateStatsForFreeList(NULL)
, _largeObjectCollectorAllocateStatsForFreeList(NULL)
{
}
/*
* Friends
*/
};
#endif /* MEMORYPOOLSPLITADDRESSORDEREDLISTBASE_HPP_ */