Wed, 23 Dec 2009 09:23:54 -0800
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
1 /*
2 * Copyright 2001-2008 Sun Microsystems, Inc. All Rights Reserved.
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 */
25 # include "incls/_precompiled.incl"
26 # include "incls/_freeList.cpp.incl"
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.
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 }
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 }
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 }
77 void FreeList::reset(size_t hint) {
78 set_count(0);
79 set_head(NULL);
80 set_tail(NULL);
81 set_hint(hint);
82 }
84 void FreeList::init_statistics(bool split_birth) {
85 _allocation_stats.initialize(split_birth);
86 }
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 }
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.");
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 }
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");
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 }
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");
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 }
215 void FreeList::returnChunkAtHead(FreeChunk* chunk) {
216 assert_proper_lock_protection();
217 returnChunkAtHead(chunk, true);
218 }
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");
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 }
249 void FreeList::returnChunkAtTail(FreeChunk* chunk) {
250 returnChunkAtTail(chunk, true);
251 }
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 }
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 }
294 #ifndef PRODUCT
295 void FreeList::verify_stats() const {
296 // The +1 of the LH comparand is to allow some "looseness" in
297 // checking: we usually call this interface when adding a block
298 // and we'll subsequently update the stats; we cannot update the
299 // stats beforehand because in the case of the large-block BT
300 // dictionary for example, this might be the first block and
301 // in that case there would be no place that we could record
302 // the stats (which are kept in the block itself).
303 assert(_allocation_stats.prevSweep() + _allocation_stats.splitBirths() + 1 // Total Stock + 1
304 >= _allocation_stats.splitDeaths() + (ssize_t)count(), "Conservation Principle");
305 }
307 void FreeList::assert_proper_lock_protection_work() const {
308 assert(_protecting_lock != NULL, "Don't call this directly");
309 assert(ParallelGCThreads > 0, "Don't call this directly");
310 Thread* thr = Thread::current();
311 if (thr->is_VM_thread() || thr->is_ConcurrentGC_thread()) {
312 // assert that we are holding the freelist lock
313 } else if (thr->is_GC_task_thread()) {
314 assert(_protecting_lock->owned_by_self(), "FreeList RACE DETECTED");
315 } else if (thr->is_Java_thread()) {
316 assert(!SafepointSynchronize::is_at_safepoint(), "Should not be executing");
317 } else {
318 ShouldNotReachHere(); // unaccounted thread type?
319 }
320 }
321 #endif
323 // Print the "label line" for free list stats.
324 void FreeList::print_labels_on(outputStream* st, const char* c) {
325 st->print("%16s\t", c);
326 st->print("%14s\t" "%14s\t" "%14s\t" "%14s\t" "%14s\t"
327 "%14s\t" "%14s\t" "%14s\t" "%14s\t" "%14s\t" "\n",
328 "bfrsurp", "surplus", "desired", "prvSwep", "bfrSwep",
329 "count", "cBirths", "cDeaths", "sBirths", "sDeaths");
330 }
332 // Print the AllocationStats for the given free list. If the second argument
333 // to the call is a non-null string, it is printed in the first column;
334 // otherwise, if the argument is null (the default), then the size of the
335 // (free list) block is printed in the first column.
336 void FreeList::print_on(outputStream* st, const char* c) const {
337 if (c != NULL) {
338 st->print("%16s", c);
339 } else {
340 st->print(SIZE_FORMAT_W(16), size());
341 }
342 st->print("\t"
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"
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",
345 bfrSurp(), surplus(), desired(), prevSweep(), beforeSweep(),
346 count(), coalBirths(), coalDeaths(), splitBirths(), splitDeaths());
347 }