Fri, 25 Jan 2013 15:06:18 -0500
6479360: PrintClassHistogram improvements
Summary: jcmd <pid> GC.class_stats (UnlockDiagnosticVMOptions)
Reviewed-by: coleenp, hseigel, sla, acorn
Contributed-by: ioi.lam@oracle.com
1 /*
2 * Copyright (c) 2001, 2012, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
25 #ifndef SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP
26 #define SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP
28 #include "memory/freeBlockDictionary.hpp"
29 #include "memory/freeList.hpp"
31 /*
32 * A binary tree based search structure for free blocks.
33 * This is currently used in the Concurrent Mark&Sweep implementation, but
34 * will be used for free block management for metadata.
35 */
37 // A TreeList is a FreeList which can be used to maintain a
38 // binary tree of free lists.
40 template <class Chunk_t, template <class> class FreeList_t> class TreeChunk;
41 template <class Chunk_t, template <class> class FreeList_t> class BinaryTreeDictionary;
42 template <class Chunk_t, template <class> class FreeList_t> class AscendTreeCensusClosure;
43 template <class Chunk_t, template <class> class FreeList_t> class DescendTreeCensusClosure;
44 template <class Chunk_t, template <class> class FreeList_t> class DescendTreeSearchClosure;
46 template <class Chunk_t, template <class> class FreeList_t>
47 class TreeList : public FreeList_t<Chunk_t> {
48 friend class TreeChunk<Chunk_t, FreeList_t>;
49 friend class BinaryTreeDictionary<Chunk_t, FreeList_t>;
50 friend class AscendTreeCensusClosure<Chunk_t, FreeList_t>;
51 friend class DescendTreeCensusClosure<Chunk_t, FreeList_t>;
52 friend class DescendTreeSearchClosure<Chunk_t, FreeList_t>;
54 TreeList<Chunk_t, FreeList_t>* _parent;
55 TreeList<Chunk_t, FreeList_t>* _left;
56 TreeList<Chunk_t, FreeList_t>* _right;
58 protected:
60 TreeList<Chunk_t, FreeList_t>* parent() const { return _parent; }
61 TreeList<Chunk_t, FreeList_t>* left() const { return _left; }
62 TreeList<Chunk_t, FreeList_t>* right() const { return _right; }
64 // Wrapper on call to base class, to get the template to compile.
65 Chunk_t* head() const { return FreeList_t<Chunk_t>::head(); }
66 Chunk_t* tail() const { return FreeList_t<Chunk_t>::tail(); }
67 void set_head(Chunk_t* head) { FreeList_t<Chunk_t>::set_head(head); }
68 void set_tail(Chunk_t* tail) { FreeList_t<Chunk_t>::set_tail(tail); }
70 size_t size() const { return FreeList_t<Chunk_t>::size(); }
72 // Accessors for links in tree.
74 void set_left(TreeList<Chunk_t, FreeList_t>* tl) {
75 _left = tl;
76 if (tl != NULL)
77 tl->set_parent(this);
78 }
79 void set_right(TreeList<Chunk_t, FreeList_t>* tl) {
80 _right = tl;
81 if (tl != NULL)
82 tl->set_parent(this);
83 }
84 void set_parent(TreeList<Chunk_t, FreeList_t>* tl) { _parent = tl; }
86 void clear_left() { _left = NULL; }
87 void clear_right() { _right = NULL; }
88 void clear_parent() { _parent = NULL; }
89 void initialize() { clear_left(); clear_right(), clear_parent(); FreeList_t<Chunk_t>::initialize(); }
91 // For constructing a TreeList from a Tree chunk or
92 // address and size.
93 TreeList();
94 static TreeList<Chunk_t, FreeList_t>*
95 as_TreeList(TreeChunk<Chunk_t, FreeList_t>* tc);
96 static TreeList<Chunk_t, FreeList_t>* as_TreeList(HeapWord* addr, size_t size);
98 // Returns the head of the free list as a pointer to a TreeChunk.
99 TreeChunk<Chunk_t, FreeList_t>* head_as_TreeChunk();
101 // Returns the first available chunk in the free list as a pointer
102 // to a TreeChunk.
103 TreeChunk<Chunk_t, FreeList_t>* first_available();
105 // Returns the block with the largest heap address amongst
106 // those in the list for this size; potentially slow and expensive,
107 // use with caution!
108 TreeChunk<Chunk_t, FreeList_t>* largest_address();
110 TreeList<Chunk_t, FreeList_t>* get_better_list(
111 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary);
113 // remove_chunk_replace_if_needed() removes the given "tc" from the TreeList.
114 // If "tc" is the first chunk in the list, it is also the
115 // TreeList that is the node in the tree. remove_chunk_replace_if_needed()
116 // returns the possibly replaced TreeList* for the node in
117 // the tree. It also updates the parent of the original
118 // node to point to the new node.
119 TreeList<Chunk_t, FreeList_t>* remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc);
120 // See FreeList.
121 void return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* tc);
122 void return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* tc);
123 };
125 // A TreeChunk is a subclass of a Chunk that additionally
126 // maintains a pointer to the free list on which it is currently
127 // linked.
128 // A TreeChunk is also used as a node in the binary tree. This
129 // allows the binary tree to be maintained without any additional
130 // storage (the free chunks are used). In a binary tree the first
131 // chunk in the free list is also the tree node. Note that the
132 // TreeChunk has an embedded TreeList for this purpose. Because
133 // the first chunk in the list is distinguished in this fashion
134 // (also is the node in the tree), it is the last chunk to be found
135 // on the free list for a node in the tree and is only removed if
136 // it is the last chunk on the free list.
138 template <class Chunk_t, template <class> class FreeList_t>
139 class TreeChunk : public Chunk_t {
140 friend class TreeList<Chunk_t, FreeList_t>;
141 TreeList<Chunk_t, FreeList_t>* _list;
142 TreeList<Chunk_t, FreeList_t> _embedded_list; // if non-null, this chunk is on _list
144 static size_t _min_tree_chunk_size;
146 protected:
147 TreeList<Chunk_t, FreeList_t>* embedded_list() const { return (TreeList<Chunk_t, FreeList_t>*) &_embedded_list; }
148 void set_embedded_list(TreeList<Chunk_t, FreeList_t>* v) { _embedded_list = *v; }
149 public:
150 TreeList<Chunk_t, FreeList_t>* list() { return _list; }
151 void set_list(TreeList<Chunk_t, FreeList_t>* v) { _list = v; }
152 static TreeChunk<Chunk_t, FreeList_t>* as_TreeChunk(Chunk_t* fc);
153 // Initialize fields in a TreeChunk that should be
154 // initialized when the TreeChunk is being added to
155 // a free list in the tree.
156 void initialize() { embedded_list()->initialize(); }
158 Chunk_t* next() const { return Chunk_t::next(); }
159 Chunk_t* prev() const { return Chunk_t::prev(); }
160 size_t size() const volatile { return Chunk_t::size(); }
162 static size_t min_size() {
163 return _min_tree_chunk_size;
164 }
166 // debugging
167 void verify_tree_chunk_list() const;
168 void assert_is_mangled() const;
169 };
172 template <class Chunk_t, template <class> class FreeList_t>
173 class BinaryTreeDictionary: public FreeBlockDictionary<Chunk_t> {
174 friend class VMStructs;
175 size_t _total_size;
176 size_t _total_free_blocks;
177 TreeList<Chunk_t, FreeList_t>* _root;
179 // private accessors
180 void set_total_size(size_t v) { _total_size = v; }
181 virtual void inc_total_size(size_t v);
182 virtual void dec_total_size(size_t v);
183 void set_total_free_blocks(size_t v) { _total_free_blocks = v; }
184 TreeList<Chunk_t, FreeList_t>* root() const { return _root; }
185 void set_root(TreeList<Chunk_t, FreeList_t>* v) { _root = v; }
187 // This field is added and can be set to point to the
188 // the Mutex used to synchronize access to the
189 // dictionary so that assertion checking can be done.
190 // For example it is set to point to _parDictionaryAllocLock.
191 NOT_PRODUCT(Mutex* _lock;)
193 // Remove a chunk of size "size" or larger from the tree and
194 // return it. If the chunk
195 // is the last chunk of that size, remove the node for that size
196 // from the tree.
197 TreeChunk<Chunk_t, FreeList_t>* get_chunk_from_tree(size_t size, enum FreeBlockDictionary<Chunk_t>::Dither dither);
198 // Remove this chunk from the tree. If the removal results
199 // in an empty list in the tree, remove the empty list.
200 TreeChunk<Chunk_t, FreeList_t>* remove_chunk_from_tree(TreeChunk<Chunk_t, FreeList_t>* tc);
201 // Remove the node in the trees starting at tl that has the
202 // minimum value and return it. Repair the tree as needed.
203 TreeList<Chunk_t, FreeList_t>* remove_tree_minimum(TreeList<Chunk_t, FreeList_t>* tl);
204 // Add this free chunk to the tree.
205 void insert_chunk_in_tree(Chunk_t* freeChunk);
206 public:
208 // Return a list of the specified size or NULL from the tree.
209 // The list is not removed from the tree.
210 TreeList<Chunk_t, FreeList_t>* find_list (size_t size) const;
212 void verify_tree() const;
213 // verify that the given chunk is in the tree.
214 bool verify_chunk_in_free_list(Chunk_t* tc) const;
215 private:
216 void verify_tree_helper(TreeList<Chunk_t, FreeList_t>* tl) const;
217 static size_t verify_prev_free_ptrs(TreeList<Chunk_t, FreeList_t>* tl);
219 // Returns the total number of chunks in the list.
220 size_t total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const;
221 // Returns the total number of words in the chunks in the tree
222 // starting at "tl".
223 size_t total_size_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const;
224 // Returns the sum of the square of the size of each block
225 // in the tree starting at "tl".
226 double sum_of_squared_block_sizes(TreeList<Chunk_t, FreeList_t>* const tl) const;
227 // Returns the total number of free blocks in the tree starting
228 // at "tl".
229 size_t total_free_blocks_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const;
230 size_t num_free_blocks() const;
231 size_t tree_height() const;
232 size_t tree_height_helper(TreeList<Chunk_t, FreeList_t>* tl) const;
233 size_t total_nodes_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const;
234 size_t total_nodes_helper(TreeList<Chunk_t, FreeList_t>* tl) const;
236 public:
237 // Constructor
238 BinaryTreeDictionary() :
239 _total_size(0), _total_free_blocks(0), _root(0) {}
241 BinaryTreeDictionary(MemRegion mr);
243 // Public accessors
244 size_t total_size() const { return _total_size; }
245 size_t total_free_blocks() const { return _total_free_blocks; }
247 // Reset the dictionary to the initial conditions with
248 // a single free chunk.
249 void reset(MemRegion mr);
250 void reset(HeapWord* addr, size_t size);
251 // Reset the dictionary to be empty.
252 void reset();
254 // Return a chunk of size "size" or greater from
255 // the tree.
256 Chunk_t* get_chunk(size_t size, enum FreeBlockDictionary<Chunk_t>::Dither dither) {
257 FreeBlockDictionary<Chunk_t>::verify_par_locked();
258 Chunk_t* res = get_chunk_from_tree(size, dither);
259 assert(res == NULL || res->is_free(),
260 "Should be returning a free chunk");
261 assert(dither != FreeBlockDictionary<Chunk_t>::exactly ||
262 res == NULL || res->size() == size, "Not correct size");
263 return res;
264 }
266 void return_chunk(Chunk_t* chunk) {
267 FreeBlockDictionary<Chunk_t>::verify_par_locked();
268 insert_chunk_in_tree(chunk);
269 }
271 void remove_chunk(Chunk_t* chunk) {
272 FreeBlockDictionary<Chunk_t>::verify_par_locked();
273 remove_chunk_from_tree((TreeChunk<Chunk_t, FreeList_t>*)chunk);
274 assert(chunk->is_free(), "Should still be a free chunk");
275 }
277 size_t max_chunk_size() const;
278 size_t total_chunk_size(debug_only(const Mutex* lock)) const {
279 debug_only(
280 if (lock != NULL && lock->owned_by_self()) {
281 assert(total_size_in_tree(root()) == total_size(),
282 "_total_size inconsistency");
283 }
284 )
285 return total_size();
286 }
288 size_t min_size() const {
289 return TreeChunk<Chunk_t, FreeList_t>::min_size();
290 }
292 double sum_of_squared_block_sizes() const {
293 return sum_of_squared_block_sizes(root());
294 }
296 Chunk_t* find_chunk_ends_at(HeapWord* target) const;
298 // Find the list with size "size" in the binary tree and update
299 // the statistics in the list according to "split" (chunk was
300 // split or coalesce) and "birth" (chunk was added or removed).
301 void dict_census_update(size_t size, bool split, bool birth);
302 // Return true if the dictionary is overpopulated (more chunks of
303 // this size than desired) for size "size".
304 bool coal_dict_over_populated(size_t size);
305 // Methods called at the beginning of a sweep to prepare the
306 // statistics for the sweep.
307 void begin_sweep_dict_census(double coalSurplusPercent,
308 float inter_sweep_current,
309 float inter_sweep_estimate,
310 float intra_sweep_estimate);
311 // Methods called after the end of a sweep to modify the
312 // statistics for the sweep.
313 void end_sweep_dict_census(double splitSurplusPercent);
314 // Return the largest free chunk in the tree.
315 Chunk_t* find_largest_dict() const;
316 // Accessors for statistics
317 void set_tree_surplus(double splitSurplusPercent);
318 void set_tree_hints(void);
319 // Reset statistics for all the lists in the tree.
320 void clear_tree_census(void);
321 // Print the statistcis for all the lists in the tree. Also may
322 // print out summaries.
323 void print_dict_census(void) const;
324 void print_free_lists(outputStream* st) const;
326 // For debugging. Returns the sum of the _returned_bytes for
327 // all lists in the tree.
328 size_t sum_dict_returned_bytes() PRODUCT_RETURN0;
329 // Sets the _returned_bytes for all the lists in the tree to zero.
330 void initialize_dict_returned_bytes() PRODUCT_RETURN;
331 // For debugging. Return the total number of chunks in the dictionary.
332 size_t total_count() PRODUCT_RETURN0;
334 void report_statistics() const;
336 void verify() const;
337 };
339 #endif // SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP