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