Mercurial > hg > graal-jvmci-8
annotate src/share/vm/gc_implementation/concurrentMarkSweep/freeList.cpp @ 1145:e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
Summary: Autonomic per-worker free block cache sizing, tunable coalition policies, fixes to per-size block statistics, retuned gain and bandwidth of some feedback loop filters to allow quicker reactivity to abrupt changes in ambient demand, and other heuristics to reduce fragmentation of the CMS old gen. Also tightened some assertions, including those related to locking.
Reviewed-by: jmasa
author | ysr |
---|---|
date | Wed, 23 Dec 2009 09:23:54 -0800 |
parents | d1605aabd0a1 |
children | c18cbe5936b8 |
rev | line source |
---|---|
0 | 1 /* |
196 | 2 * Copyright 2001-2008 Sun Microsystems, Inc. All Rights Reserved. |
0 | 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 * | |
5 * This code is free software; you can redistribute it and/or modify it | |
6 * under the terms of the GNU General Public License version 2 only, as | |
7 * published by the Free Software Foundation. | |
8 * | |
9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
12 * version 2 for more details (a copy is included in the LICENSE file that | |
13 * accompanied this code). | |
14 * | |
15 * You should have received a copy of the GNU General Public License version | |
16 * 2 along with this work; if not, write to the Free Software Foundation, | |
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
18 * | |
19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, | |
20 * CA 95054 USA or visit www.sun.com if you need additional information or | |
21 * have any questions. | |
22 * | |
23 */ | |
24 | |
25 # include "incls/_precompiled.incl" | |
26 # include "incls/_freeList.cpp.incl" | |
27 | |
28 // Free list. A FreeList is used to access a linked list of chunks | |
29 // of space in the heap. The head and tail are maintained so that | |
30 // items can be (as in the current implementation) added at the | |
31 // at the tail of the list and removed from the head of the list to | |
32 // maintain a FIFO queue. | |
33 | |
34 FreeList::FreeList() : | |
35 _head(NULL), _tail(NULL) | |
36 #ifdef ASSERT | |
37 , _protecting_lock(NULL) | |
38 #endif | |
39 { | |
40 _size = 0; | |
41 _count = 0; | |
42 _hint = 0; | |
43 init_statistics(); | |
44 } | |
45 | |
46 FreeList::FreeList(FreeChunk* fc) : | |
47 _head(fc), _tail(fc) | |
48 #ifdef ASSERT | |
49 , _protecting_lock(NULL) | |
50 #endif | |
51 { | |
52 _size = fc->size(); | |
53 _count = 1; | |
54 _hint = 0; | |
55 init_statistics(); | |
56 #ifndef PRODUCT | |
57 _allocation_stats.set_returnedBytes(size() * HeapWordSize); | |
58 #endif | |
59 } | |
60 | |
61 FreeList::FreeList(HeapWord* addr, size_t size) : | |
62 _head((FreeChunk*) addr), _tail((FreeChunk*) addr) | |
63 #ifdef ASSERT | |
64 , _protecting_lock(NULL) | |
65 #endif | |
66 { | |
67 assert(size > sizeof(FreeChunk), "size is too small"); | |
68 head()->setSize(size); | |
69 _size = size; | |
70 _count = 1; | |
71 init_statistics(); | |
72 #ifndef PRODUCT | |
73 _allocation_stats.set_returnedBytes(_size * HeapWordSize); | |
74 #endif | |
75 } | |
76 | |
77 void FreeList::reset(size_t hint) { | |
78 set_count(0); | |
79 set_head(NULL); | |
80 set_tail(NULL); | |
81 set_hint(hint); | |
82 } | |
83 | |
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
84 void FreeList::init_statistics(bool split_birth) { |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
85 _allocation_stats.initialize(split_birth); |
0 | 86 } |
87 | |
88 FreeChunk* FreeList::getChunkAtHead() { | |
89 assert_proper_lock_protection(); | |
90 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | |
91 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
92 FreeChunk* fc = head(); | |
93 if (fc != NULL) { | |
94 FreeChunk* nextFC = fc->next(); | |
95 if (nextFC != NULL) { | |
96 // The chunk fc being removed has a "next". Set the "next" to the | |
97 // "prev" of fc. | |
98 nextFC->linkPrev(NULL); | |
99 } else { // removed tail of list | |
100 link_tail(NULL); | |
101 } | |
102 link_head(nextFC); | |
103 decrement_count(); | |
104 } | |
105 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | |
106 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
107 return fc; | |
108 } | |
109 | |
110 | |
111 void FreeList::getFirstNChunksFromList(size_t n, FreeList* fl) { | |
112 assert_proper_lock_protection(); | |
113 assert(fl->count() == 0, "Precondition"); | |
114 if (count() > 0) { | |
115 int k = 1; | |
116 fl->set_head(head()); n--; | |
117 FreeChunk* tl = head(); | |
118 while (tl->next() != NULL && n > 0) { | |
119 tl = tl->next(); n--; k++; | |
120 } | |
121 assert(tl != NULL, "Loop Inv."); | |
122 | |
123 // First, fix up the list we took from. | |
124 FreeChunk* new_head = tl->next(); | |
125 set_head(new_head); | |
126 set_count(count() - k); | |
127 if (new_head == NULL) { | |
128 set_tail(NULL); | |
129 } else { | |
130 new_head->linkPrev(NULL); | |
131 } | |
132 // Now we can fix up the tail. | |
133 tl->linkNext(NULL); | |
134 // And return the result. | |
135 fl->set_tail(tl); | |
136 fl->set_count(k); | |
137 } | |
138 } | |
139 | |
140 // Remove this chunk from the list | |
141 void FreeList::removeChunk(FreeChunk*fc) { | |
142 assert_proper_lock_protection(); | |
143 assert(head() != NULL, "Remove from empty list"); | |
144 assert(fc != NULL, "Remove a NULL chunk"); | |
145 assert(size() == fc->size(), "Wrong list"); | |
146 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | |
147 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
148 | |
149 FreeChunk* prevFC = fc->prev(); | |
150 FreeChunk* nextFC = fc->next(); | |
151 if (nextFC != NULL) { | |
152 // The chunk fc being removed has a "next". Set the "next" to the | |
153 // "prev" of fc. | |
154 nextFC->linkPrev(prevFC); | |
155 } else { // removed tail of list | |
156 link_tail(prevFC); | |
157 } | |
158 if (prevFC == NULL) { // removed head of list | |
159 link_head(nextFC); | |
160 assert(nextFC == NULL || nextFC->prev() == NULL, | |
161 "Prev of head should be NULL"); | |
162 } else { | |
163 prevFC->linkNext(nextFC); | |
164 assert(tail() != prevFC || prevFC->next() == NULL, | |
165 "Next of tail should be NULL"); | |
166 } | |
167 decrement_count(); | |
168 #define TRAP_CODE 1 | |
169 #if TRAP_CODE | |
170 if (head() == NULL) { | |
171 guarantee(tail() == NULL, "INVARIANT"); | |
172 guarantee(count() == 0, "INVARIANT"); | |
173 } | |
174 #endif | |
175 // clear next and prev fields of fc, debug only | |
176 NOT_PRODUCT( | |
177 fc->linkPrev(NULL); | |
178 fc->linkNext(NULL); | |
179 ) | |
180 assert(fc->isFree(), "Should still be a free chunk"); | |
181 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | |
182 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
183 assert(head() == NULL || head()->size() == size(), "wrong item on list"); | |
184 assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); | |
185 } | |
186 | |
187 // Add this chunk at the head of the list. | |
188 void FreeList::returnChunkAtHead(FreeChunk* chunk, bool record_return) { | |
189 assert_proper_lock_protection(); | |
190 assert(chunk != NULL, "insert a NULL chunk"); | |
191 assert(size() == chunk->size(), "Wrong size"); | |
192 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | |
193 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
194 | |
195 FreeChunk* oldHead = head(); | |
196 assert(chunk != oldHead, "double insertion"); | |
197 chunk->linkAfter(oldHead); | |
198 link_head(chunk); | |
199 if (oldHead == NULL) { // only chunk in list | |
200 assert(tail() == NULL, "inconsistent FreeList"); | |
201 link_tail(chunk); | |
202 } | |
203 increment_count(); // of # of chunks in list | |
204 DEBUG_ONLY( | |
205 if (record_return) { | |
206 increment_returnedBytes_by(size()*HeapWordSize); | |
207 } | |
208 ) | |
209 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | |
210 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
211 assert(head() == NULL || head()->size() == size(), "wrong item on list"); | |
212 assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); | |
213 } | |
214 | |
215 void FreeList::returnChunkAtHead(FreeChunk* chunk) { | |
216 assert_proper_lock_protection(); | |
217 returnChunkAtHead(chunk, true); | |
218 } | |
219 | |
220 // Add this chunk at the tail of the list. | |
221 void FreeList::returnChunkAtTail(FreeChunk* chunk, bool record_return) { | |
222 assert_proper_lock_protection(); | |
223 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | |
224 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
225 assert(chunk != NULL, "insert a NULL chunk"); | |
226 assert(size() == chunk->size(), "wrong size"); | |
227 | |
228 FreeChunk* oldTail = tail(); | |
229 assert(chunk != oldTail, "double insertion"); | |
230 if (oldTail != NULL) { | |
231 oldTail->linkAfter(chunk); | |
232 } else { // only chunk in list | |
233 assert(head() == NULL, "inconsistent FreeList"); | |
234 link_head(chunk); | |
235 } | |
236 link_tail(chunk); | |
237 increment_count(); // of # of chunks in list | |
238 DEBUG_ONLY( | |
239 if (record_return) { | |
240 increment_returnedBytes_by(size()*HeapWordSize); | |
241 } | |
242 ) | |
243 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | |
244 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
245 assert(head() == NULL || head()->size() == size(), "wrong item on list"); | |
246 assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); | |
247 } | |
248 | |
249 void FreeList::returnChunkAtTail(FreeChunk* chunk) { | |
250 returnChunkAtTail(chunk, true); | |
251 } | |
252 | |
253 void FreeList::prepend(FreeList* fl) { | |
254 assert_proper_lock_protection(); | |
255 if (fl->count() > 0) { | |
256 if (count() == 0) { | |
257 set_head(fl->head()); | |
258 set_tail(fl->tail()); | |
259 set_count(fl->count()); | |
260 } else { | |
261 // Both are non-empty. | |
262 FreeChunk* fl_tail = fl->tail(); | |
263 FreeChunk* this_head = head(); | |
264 assert(fl_tail->next() == NULL, "Well-formedness of fl"); | |
265 fl_tail->linkNext(this_head); | |
266 this_head->linkPrev(fl_tail); | |
267 set_head(fl->head()); | |
268 set_count(count() + fl->count()); | |
269 } | |
270 fl->set_head(NULL); | |
271 fl->set_tail(NULL); | |
272 fl->set_count(0); | |
273 } | |
274 } | |
275 | |
276 // verifyChunkInFreeLists() is used to verify that an item is in this free list. | |
277 // It is used as a debugging aid. | |
278 bool FreeList::verifyChunkInFreeLists(FreeChunk* fc) const { | |
279 // This is an internal consistency check, not part of the check that the | |
280 // chunk is in the free lists. | |
281 guarantee(fc->size() == size(), "Wrong list is being searched"); | |
282 FreeChunk* curFC = head(); | |
283 while (curFC) { | |
284 // This is an internal consistency check. | |
285 guarantee(size() == curFC->size(), "Chunk is in wrong list."); | |
286 if (fc == curFC) { | |
287 return true; | |
288 } | |
289 curFC = curFC->next(); | |
290 } | |
291 return false; | |
292 } | |
293 | |
294 #ifndef PRODUCT | |
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
295 void FreeList::verify_stats() const { |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
296 // The +1 of the LH comparand is to allow some "looseness" in |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
297 // checking: we usually call this interface when adding a block |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
298 // and we'll subsequently update the stats; we cannot update the |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
299 // stats beforehand because in the case of the large-block BT |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
300 // dictionary for example, this might be the first block and |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
301 // in that case there would be no place that we could record |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
302 // the stats (which are kept in the block itself). |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
303 assert(_allocation_stats.prevSweep() + _allocation_stats.splitBirths() + 1 // Total Stock + 1 |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
304 >= _allocation_stats.splitDeaths() + (ssize_t)count(), "Conservation Principle"); |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
305 } |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
306 |
0 | 307 void FreeList::assert_proper_lock_protection_work() const { |
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
308 assert(_protecting_lock != NULL, "Don't call this directly"); |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
309 assert(ParallelGCThreads > 0, "Don't call this directly"); |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
310 Thread* thr = Thread::current(); |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
311 if (thr->is_VM_thread() || thr->is_ConcurrentGC_thread()) { |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
312 // assert that we are holding the freelist lock |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
313 } else if (thr->is_GC_task_thread()) { |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
314 assert(_protecting_lock->owned_by_self(), "FreeList RACE DETECTED"); |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
315 } else if (thr->is_Java_thread()) { |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
316 assert(!SafepointSynchronize::is_at_safepoint(), "Should not be executing"); |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
317 } else { |
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
196
diff
changeset
|
318 ShouldNotReachHere(); // unaccounted thread type? |
0 | 319 } |
320 } | |
321 #endif | |
12
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
322 |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
323 // Print the "label line" for free list stats. |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
324 void FreeList::print_labels_on(outputStream* st, const char* c) { |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
325 st->print("%16s\t", c); |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
326 st->print("%14s\t" "%14s\t" "%14s\t" "%14s\t" "%14s\t" |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
327 "%14s\t" "%14s\t" "%14s\t" "%14s\t" "%14s\t" "\n", |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
328 "bfrsurp", "surplus", "desired", "prvSwep", "bfrSwep", |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
329 "count", "cBirths", "cDeaths", "sBirths", "sDeaths"); |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
330 } |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
331 |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
332 // Print the AllocationStats for the given free list. If the second argument |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
333 // to the call is a non-null string, it is printed in the first column; |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
334 // otherwise, if the argument is null (the default), then the size of the |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
335 // (free list) block is printed in the first column. |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
336 void FreeList::print_on(outputStream* st, const char* c) const { |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
337 if (c != NULL) { |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
338 st->print("%16s", c); |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
339 } else { |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
340 st->print(SIZE_FORMAT_W(16), size()); |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
341 } |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
342 st->print("\t" |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
343 SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
344 SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\n", |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
345 bfrSurp(), surplus(), desired(), prevSweep(), beforeSweep(), |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
346 count(), coalBirths(), coalDeaths(), splitBirths(), splitDeaths()); |
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
347 } |