Thu, 20 Nov 2008 16:56:09 -0800
6684579: SoftReference processing can be made more efficient
Summary: For current soft-ref clearing policies, we can decide at marking time if a soft-reference will definitely not be cleared, postponing the decision of whether it will definitely be cleared to the final reference processing phase. This can be especially beneficial in the case of concurrent collectors where the marking is usually concurrent but reference processing is usually not.
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;
45 TreeList* _parent;
46 TreeList* _left;
47 TreeList* _right;
49 protected:
50 TreeList* parent() const { return _parent; }
51 TreeList* left() const { return _left; }
52 TreeList* right() const { return _right; }
54 // Accessors for links in tree.
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; }
68 void clearLeft() { _left = NULL; }
69 void clearRight() { _right = NULL; }
70 void clearParent() { _parent = NULL; }
71 void initialize() { clearLeft(); clearRight(), clearParent(); }
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);
78 // Returns the head of the free list as a pointer to a TreeChunk.
79 TreeChunk* head_as_TreeChunk();
81 // Returns the first available chunk in the free list as a pointer
82 // to a TreeChunk.
83 TreeChunk* first_available();
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 };
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.
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(); }
126 // debugging
127 void verifyTreeChunkList() const;
128 };
130 const size_t MIN_TREE_CHUNK_SIZE = sizeof(TreeChunk)/HeapWordSize;
132 class BinaryTreeDictionary: public FreeBlockDictionary {
133 friend class VMStructs;
134 bool _splay;
135 size_t _totalSize;
136 size_t _totalFreeBlocks;
137 TreeList* _root;
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; }
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);
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;
193 public:
194 // Constructor
195 BinaryTreeDictionary(MemRegion mr, bool splay = false);
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();
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 }
215 void returnChunk(FreeChunk* chunk) {
216 verify_par_locked();
217 insertChunkInTree(chunk);
218 }
220 void removeChunk(FreeChunk* chunk) {
221 verify_par_locked();
222 removeChunkFromTree((TreeChunk*)chunk);
223 assert(chunk->isFree(), "Should still be a free chunk");
224 }
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 }
237 size_t minSize() const {
238 return MIN_TREE_CHUNK_SIZE;
239 }
241 double sum_of_squared_block_sizes() const {
242 return sum_of_squared_block_sizes(root());
243 }
245 FreeChunk* find_chunk_ends_at(HeapWord* target) const;
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;
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;
281 void reportStatistics() const;
283 void verify() const;
284 };