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 /*
26 * A binary tree based search structure for free blocks.
27 * This is currently used in the Concurrent Mark&Sweep implementation.
28 */
30 // A TreeList is a FreeList which can be used to maintain a
31 // binary tree of free lists.
33 class TreeChunk;
34 class BinaryTreeDictionary;
35 class AscendTreeCensusClosure;
36 class DescendTreeCensusClosure;
37 class DescendTreeSearchClosure;
39 class TreeList: public FreeList {
40 friend class TreeChunk;
41 friend class BinaryTreeDictionary;
42 friend class AscendTreeCensusClosure;
43 friend class DescendTreeCensusClosure;
44 friend class DescendTreeSearchClosure;
46 protected:
47 TreeList* parent() const { return _parent; }
48 TreeList* left() const { return _left; }
49 TreeList* right() const { return _right; }
51 // Accessors for links in tree.
53 void setLeft(TreeList* tl) {
54 _left = tl;
55 if (tl != NULL)
56 tl->setParent(this);
57 }
58 void setRight(TreeList* tl) {
59 _right = tl;
60 if (tl != NULL)
61 tl->setParent(this);
62 }
63 void setParent(TreeList* tl) { _parent = tl; }
65 void clearLeft() { _left = NULL; }
66 void clearRight() { _right = NULL; }
67 void clearParent() { _parent = NULL; }
68 void initialize() { clearLeft(); clearRight(), clearParent(); }
70 // For constructing a TreeList from a Tree chunk or
71 // address and size.
72 static TreeList* as_TreeList(TreeChunk* tc);
73 static TreeList* as_TreeList(HeapWord* addr, size_t size);
75 // Returns the head of the free list as a pointer to a TreeChunk.
76 TreeChunk* head_as_TreeChunk();
78 // Returns the first available chunk in the free list as a pointer
79 // to a TreeChunk.
80 TreeChunk* first_available();
82 // Returns the block with the largest heap address amongst
83 // those in the list for this size; potentially slow and expensive,
84 // use with caution!
85 TreeChunk* largest_address();
87 // removeChunkReplaceIfNeeded() removes the given "tc" from the TreeList.
88 // If "tc" is the first chunk in the list, it is also the
89 // TreeList that is the node in the tree. removeChunkReplaceIfNeeded()
90 // returns the possibly replaced TreeList* for the node in
91 // the tree. It also updates the parent of the original
92 // node to point to the new node.
93 TreeList* removeChunkReplaceIfNeeded(TreeChunk* tc);
94 // See FreeList.
95 void returnChunkAtHead(TreeChunk* tc);
96 void returnChunkAtTail(TreeChunk* tc);
97 };
99 // A TreeChunk is a subclass of a FreeChunk that additionally
100 // maintains a pointer to the free list on which it is currently
101 // linked.
102 // A TreeChunk is also used as a node in the binary tree. This
103 // allows the binary tree to be maintained without any additional
104 // storage (the free chunks are used). In a binary tree the first
105 // chunk in the free list is also the tree node. Note that the
106 // TreeChunk has an embedded TreeList for this purpose. Because
107 // the first chunk in the list is distinguished in this fashion
108 // (also is the node in the tree), it is the last chunk to be found
109 // on the free list for a node in the tree and is only removed if
110 // it is the last chunk on the free list.
112 class TreeChunk : public FreeChunk {
113 friend class TreeList;
114 TreeList* _list;
115 TreeList _embedded_list; // if non-null, this chunk is on _list
116 protected:
117 TreeList* embedded_list() const { return (TreeList*) &_embedded_list; }
118 void set_embedded_list(TreeList* v) { _embedded_list = *v; }
119 public:
120 TreeList* list() { return _list; }
121 void set_list(TreeList* v) { _list = v; }
122 static TreeChunk* as_TreeChunk(FreeChunk* fc);
123 // Initialize fields in a TreeChunk that should be
124 // initialized when the TreeChunk is being added to
125 // a free list in the tree.
126 void initialize() { embedded_list()->initialize(); }
128 // debugging
129 void verifyTreeChunkList() const;
130 };
132 const size_t MIN_TREE_CHUNK_SIZE = sizeof(TreeChunk)/HeapWordSize;
134 class BinaryTreeDictionary: public FreeBlockDictionary {
135 friend class VMStructs;
136 bool _splay;
137 size_t _totalSize;
138 size_t _totalFreeBlocks;
139 TreeList* _root;
141 // private accessors
142 bool splay() const { return _splay; }
143 void set_splay(bool v) { _splay = v; }
144 size_t totalSize() const { return _totalSize; }
145 void set_totalSize(size_t v) { _totalSize = v; }
146 virtual void inc_totalSize(size_t v);
147 virtual void dec_totalSize(size_t v);
148 size_t totalFreeBlocks() const { return _totalFreeBlocks; }
149 void set_totalFreeBlocks(size_t v) { _totalFreeBlocks = v; }
150 TreeList* root() const { return _root; }
151 void set_root(TreeList* v) { _root = v; }
153 // Remove a chunk of size "size" or larger from the tree and
154 // return it. If the chunk
155 // is the last chunk of that size, remove the node for that size
156 // from the tree.
157 TreeChunk* getChunkFromTree(size_t size, Dither dither, bool splay);
158 // Return a list of the specified size or NULL from the tree.
159 // The list is not removed from the tree.
160 TreeList* findList (size_t size) const;
161 // Remove this chunk from the tree. If the removal results
162 // in an empty list in the tree, remove the empty list.
163 TreeChunk* removeChunkFromTree(TreeChunk* tc);
164 // Remove the node in the trees starting at tl that has the
165 // minimum value and return it. Repair the tree as needed.
166 TreeList* removeTreeMinimum(TreeList* tl);
167 void semiSplayStep(TreeList* tl);
168 // Add this free chunk to the tree.
169 void insertChunkInTree(FreeChunk* freeChunk);
170 public:
171 void verifyTree() const;
172 // verify that the given chunk is in the tree.
173 bool verifyChunkInFreeLists(FreeChunk* tc) const;
174 private:
175 void verifyTreeHelper(TreeList* tl) const;
176 static size_t verifyPrevFreePtrs(TreeList* tl);
178 // Returns the total number of chunks in the list.
179 size_t totalListLength(TreeList* tl) const;
180 // Returns the total number of words in the chunks in the tree
181 // starting at "tl".
182 size_t totalSizeInTree(TreeList* tl) const;
183 // Returns the sum of the square of the size of each block
184 // in the tree starting at "tl".
185 double sum_of_squared_block_sizes(TreeList* const tl) const;
186 // Returns the total number of free blocks in the tree starting
187 // at "tl".
188 size_t totalFreeBlocksInTree(TreeList* tl) const;
189 size_t numFreeBlocks() const;
190 size_t treeHeight() const;
191 size_t treeHeightHelper(TreeList* tl) const;
192 size_t totalNodesInTree(TreeList* tl) const;
193 size_t totalNodesHelper(TreeList* tl) const;
195 public:
196 // Constructor
197 BinaryTreeDictionary(MemRegion mr, bool splay = false);
199 // Reset the dictionary to the initial conditions with
200 // a single free chunk.
201 void reset(MemRegion mr);
202 void reset(HeapWord* addr, size_t size);
203 // Reset the dictionary to be empty.
204 void reset();
206 // Return a chunk of size "size" or greater from
207 // the tree.
208 // want a better dynamic splay strategy for the future.
209 FreeChunk* getChunk(size_t size, Dither dither) {
210 verify_par_locked();
211 FreeChunk* res = getChunkFromTree(size, dither, splay());
212 assert(res == NULL || res->isFree(),
213 "Should be returning a free chunk");
214 return res;
215 }
217 void returnChunk(FreeChunk* chunk) {
218 verify_par_locked();
219 insertChunkInTree(chunk);
220 }
222 void removeChunk(FreeChunk* chunk) {
223 verify_par_locked();
224 removeChunkFromTree((TreeChunk*)chunk);
225 assert(chunk->isFree(), "Should still be a free chunk");
226 }
228 size_t maxChunkSize() const;
229 size_t totalChunkSize(debug_only(const Mutex* lock)) const {
230 debug_only(
231 if (lock != NULL && lock->owned_by_self()) {
232 assert(totalSizeInTree(root()) == totalSize(),
233 "_totalSize inconsistency");
234 }
235 )
236 return totalSize();
237 }
239 size_t minSize() const {
240 return MIN_TREE_CHUNK_SIZE;
241 }
243 double sum_of_squared_block_sizes() const {
244 return sum_of_squared_block_sizes(root());
245 }
247 FreeChunk* find_chunk_ends_at(HeapWord* target) const;
249 // Find the list with size "size" in the binary tree and update
250 // the statistics in the list according to "split" (chunk was
251 // split or coalesce) and "birth" (chunk was added or removed).
252 void dictCensusUpdate(size_t size, bool split, bool birth);
253 // Return true if the dictionary is overpopulated (more chunks of
254 // this size than desired) for size "size".
255 bool coalDictOverPopulated(size_t size);
256 // Methods called at the beginning of a sweep to prepare the
257 // statistics for the sweep.
258 void beginSweepDictCensus(double coalSurplusPercent,
259 float inter_sweep_current,
260 float inter_sweep_estimate,
261 float intra_sweep_estimate);
262 // Methods called after the end of a sweep to modify the
263 // statistics for the sweep.
264 void endSweepDictCensus(double splitSurplusPercent);
265 // Return the largest free chunk in the tree.
266 FreeChunk* findLargestDict() const;
267 // Accessors for statistics
268 void setTreeSurplus(double splitSurplusPercent);
269 void setTreeHints(void);
270 // Reset statistics for all the lists in the tree.
271 void clearTreeCensus(void);
272 // Print the statistcis for all the lists in the tree. Also may
273 // print out summaries.
274 void printDictCensus(void) const;
275 void print_free_lists(outputStream* st) const;
277 // For debugging. Returns the sum of the _returnedBytes for
278 // all lists in the tree.
279 size_t sumDictReturnedBytes() PRODUCT_RETURN0;
280 // Sets the _returnedBytes for all the lists in the tree to zero.
281 void initializeDictReturnedBytes() PRODUCT_RETURN;
282 // For debugging. Return the total number of chunks in the dictionary.
283 size_t totalCount() PRODUCT_RETURN0;
285 void reportStatistics() const;
287 void verify() const;
288 };