Tue, 11 Sep 2012 14:59:23 +0200
7197350: NPG: jvmtiHeapReferenceCallback receives incorrect reference_kind for system class roots
Summary: Fix the iteration over the system classes and report the correct reference kind.
Reviewed-by: coleenp, rbackman
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> class TreeChunk;
41 template <class Chunk> class BinaryTreeDictionary;
42 template <class Chunk> class AscendTreeCensusClosure;
43 template <class Chunk> class DescendTreeCensusClosure;
44 template <class Chunk> class DescendTreeSearchClosure;
46 template <class Chunk>
47 class TreeList: public FreeList<Chunk> {
48 friend class TreeChunk<Chunk>;
49 friend class BinaryTreeDictionary<Chunk>;
50 friend class AscendTreeCensusClosure<Chunk>;
51 friend class DescendTreeCensusClosure<Chunk>;
52 friend class DescendTreeSearchClosure<Chunk>;
54 TreeList<Chunk>* _parent;
55 TreeList<Chunk>* _left;
56 TreeList<Chunk>* _right;
58 protected:
59 TreeList<Chunk>* parent() const { return _parent; }
60 TreeList<Chunk>* left() const { return _left; }
61 TreeList<Chunk>* right() const { return _right; }
63 // Explicitly import these names into our namespace to fix name lookup with templates
64 using FreeList<Chunk>::head;
65 using FreeList<Chunk>::set_head;
67 using FreeList<Chunk>::tail;
68 using FreeList<Chunk>::set_tail;
69 using FreeList<Chunk>::link_tail;
71 using FreeList<Chunk>::increment_count;
72 NOT_PRODUCT(using FreeList<Chunk>::increment_returned_bytes_by;)
73 using FreeList<Chunk>::verify_chunk_in_free_list;
74 using FreeList<Chunk>::size;
76 // Accessors for links in tree.
78 void set_left(TreeList<Chunk>* tl) {
79 _left = tl;
80 if (tl != NULL)
81 tl->set_parent(this);
82 }
83 void set_right(TreeList<Chunk>* tl) {
84 _right = tl;
85 if (tl != NULL)
86 tl->set_parent(this);
87 }
88 void set_parent(TreeList<Chunk>* tl) { _parent = tl; }
90 void clearLeft() { _left = NULL; }
91 void clear_right() { _right = NULL; }
92 void clear_parent() { _parent = NULL; }
93 void initialize() { clearLeft(); clear_right(), clear_parent(); }
95 // For constructing a TreeList from a Tree chunk or
96 // address and size.
97 static TreeList<Chunk>* as_TreeList(TreeChunk<Chunk>* tc);
98 static TreeList<Chunk>* as_TreeList(HeapWord* addr, size_t size);
100 // Returns the head of the free list as a pointer to a TreeChunk.
101 TreeChunk<Chunk>* head_as_TreeChunk();
103 // Returns the first available chunk in the free list as a pointer
104 // to a TreeChunk.
105 TreeChunk<Chunk>* first_available();
107 // Returns the block with the largest heap address amongst
108 // those in the list for this size; potentially slow and expensive,
109 // use with caution!
110 TreeChunk<Chunk>* largest_address();
112 // remove_chunk_replace_if_needed() removes the given "tc" from the TreeList.
113 // If "tc" is the first chunk in the list, it is also the
114 // TreeList that is the node in the tree. remove_chunk_replace_if_needed()
115 // returns the possibly replaced TreeList* for the node in
116 // the tree. It also updates the parent of the original
117 // node to point to the new node.
118 TreeList<Chunk>* remove_chunk_replace_if_needed(TreeChunk<Chunk>* tc);
119 // See FreeList.
120 void return_chunk_at_head(TreeChunk<Chunk>* tc);
121 void return_chunk_at_tail(TreeChunk<Chunk>* tc);
122 };
124 // A TreeChunk is a subclass of a Chunk that additionally
125 // maintains a pointer to the free list on which it is currently
126 // linked.
127 // A TreeChunk is also used as a node in the binary tree. This
128 // allows the binary tree to be maintained without any additional
129 // storage (the free chunks are used). In a binary tree the first
130 // chunk in the free list is also the tree node. Note that the
131 // TreeChunk has an embedded TreeList for this purpose. Because
132 // the first chunk in the list is distinguished in this fashion
133 // (also is the node in the tree), it is the last chunk to be found
134 // on the free list for a node in the tree and is only removed if
135 // it is the last chunk on the free list.
137 template <class Chunk>
138 class TreeChunk : public Chunk {
139 friend class TreeList<Chunk>;
140 TreeList<Chunk>* _list;
141 TreeList<Chunk> _embedded_list; // if non-null, this chunk is on _list
142 protected:
143 TreeList<Chunk>* embedded_list() const { return (TreeList<Chunk>*) &_embedded_list; }
144 void set_embedded_list(TreeList<Chunk>* v) { _embedded_list = *v; }
145 public:
146 TreeList<Chunk>* list() { return _list; }
147 void set_list(TreeList<Chunk>* v) { _list = v; }
148 static TreeChunk<Chunk>* as_TreeChunk(Chunk* fc);
149 // Initialize fields in a TreeChunk that should be
150 // initialized when the TreeChunk is being added to
151 // a free list in the tree.
152 void initialize() { embedded_list()->initialize(); }
154 Chunk* next() const { return Chunk::next(); }
155 Chunk* prev() const { return Chunk::prev(); }
156 size_t size() const volatile { return Chunk::size(); }
158 // debugging
159 void verify_tree_chunk_list() const;
160 };
163 template <class Chunk>
164 class BinaryTreeDictionary: public FreeBlockDictionary<Chunk> {
165 friend class VMStructs;
166 bool _splay;
167 bool _adaptive_freelists;
168 size_t _total_size;
169 size_t _total_free_blocks;
170 TreeList<Chunk>* _root;
172 // private accessors
173 bool splay() const { return _splay; }
174 void set_splay(bool v) { _splay = v; }
175 void set_total_size(size_t v) { _total_size = v; }
176 virtual void inc_total_size(size_t v);
177 virtual void dec_total_size(size_t v);
178 size_t total_free_blocks() const { return _total_free_blocks; }
179 void set_total_free_blocks(size_t v) { _total_free_blocks = v; }
180 TreeList<Chunk>* root() const { return _root; }
181 void set_root(TreeList<Chunk>* v) { _root = v; }
182 bool adaptive_freelists() { return _adaptive_freelists; }
184 // This field is added and can be set to point to the
185 // the Mutex used to synchronize access to the
186 // dictionary so that assertion checking can be done.
187 // For example it is set to point to _parDictionaryAllocLock.
188 NOT_PRODUCT(Mutex* _lock;)
190 // Remove a chunk of size "size" or larger from the tree and
191 // return it. If the chunk
192 // is the last chunk of that size, remove the node for that size
193 // from the tree.
194 TreeChunk<Chunk>* get_chunk_from_tree(size_t size, enum FreeBlockDictionary<Chunk>::Dither dither, bool splay);
195 // Return a list of the specified size or NULL from the tree.
196 // The list is not removed from the tree.
197 TreeList<Chunk>* find_list (size_t size) const;
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>* remove_chunk_from_tree(TreeChunk<Chunk>* 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>* remove_tree_minimum(TreeList<Chunk>* tl);
204 void semi_splay_step(TreeList<Chunk>* tl);
205 // Add this free chunk to the tree.
206 void insert_chunk_in_tree(Chunk* freeChunk);
207 public:
209 static const size_t min_tree_chunk_size = sizeof(TreeChunk<Chunk>)/HeapWordSize;
211 void verify_tree() const;
212 // verify that the given chunk is in the tree.
213 bool verify_chunk_in_free_list(Chunk* tc) const;
214 private:
215 void verify_tree_helper(TreeList<Chunk>* tl) const;
216 static size_t verify_prev_free_ptrs(TreeList<Chunk>* tl);
218 // Returns the total number of chunks in the list.
219 size_t total_list_length(TreeList<Chunk>* tl) const;
220 // Returns the total number of words in the chunks in the tree
221 // starting at "tl".
222 size_t total_size_in_tree(TreeList<Chunk>* tl) const;
223 // Returns the sum of the square of the size of each block
224 // in the tree starting at "tl".
225 double sum_of_squared_block_sizes(TreeList<Chunk>* const tl) const;
226 // Returns the total number of free blocks in the tree starting
227 // at "tl".
228 size_t total_free_blocks_in_tree(TreeList<Chunk>* tl) const;
229 size_t num_free_blocks() const;
230 size_t treeHeight() const;
231 size_t tree_height_helper(TreeList<Chunk>* tl) const;
232 size_t total_nodes_in_tree(TreeList<Chunk>* tl) const;
233 size_t total_nodes_helper(TreeList<Chunk>* tl) const;
235 public:
236 // Constructor
237 BinaryTreeDictionary(bool adaptive_freelists, bool splay = false);
238 BinaryTreeDictionary(MemRegion mr, bool adaptive_freelists, bool splay = false);
240 // Public accessors
241 size_t total_size() const { return _total_size; }
243 // Reset the dictionary to the initial conditions with
244 // a single free chunk.
245 void reset(MemRegion mr);
246 void reset(HeapWord* addr, size_t size);
247 // Reset the dictionary to be empty.
248 void reset();
250 // Return a chunk of size "size" or greater from
251 // the tree.
252 // want a better dynamic splay strategy for the future.
253 Chunk* get_chunk(size_t size, enum FreeBlockDictionary<Chunk>::Dither dither) {
254 FreeBlockDictionary<Chunk>::verify_par_locked();
255 Chunk* res = get_chunk_from_tree(size, dither, splay());
256 assert(res == NULL || res->is_free(),
257 "Should be returning a free chunk");
258 return res;
259 }
261 void return_chunk(Chunk* chunk) {
262 FreeBlockDictionary<Chunk>::verify_par_locked();
263 insert_chunk_in_tree(chunk);
264 }
266 void remove_chunk(Chunk* chunk) {
267 FreeBlockDictionary<Chunk>::verify_par_locked();
268 remove_chunk_from_tree((TreeChunk<Chunk>*)chunk);
269 assert(chunk->is_free(), "Should still be a free chunk");
270 }
272 size_t max_chunk_size() const;
273 size_t total_chunk_size(debug_only(const Mutex* lock)) const {
274 debug_only(
275 if (lock != NULL && lock->owned_by_self()) {
276 assert(total_size_in_tree(root()) == total_size(),
277 "_total_size inconsistency");
278 }
279 )
280 return total_size();
281 }
283 size_t min_size() const {
284 return min_tree_chunk_size;
285 }
287 double sum_of_squared_block_sizes() const {
288 return sum_of_squared_block_sizes(root());
289 }
291 Chunk* find_chunk_ends_at(HeapWord* target) const;
293 // Find the list with size "size" in the binary tree and update
294 // the statistics in the list according to "split" (chunk was
295 // split or coalesce) and "birth" (chunk was added or removed).
296 void dict_census_udpate(size_t size, bool split, bool birth);
297 // Return true if the dictionary is overpopulated (more chunks of
298 // this size than desired) for size "size".
299 bool coal_dict_over_populated(size_t size);
300 // Methods called at the beginning of a sweep to prepare the
301 // statistics for the sweep.
302 void begin_sweep_dict_census(double coalSurplusPercent,
303 float inter_sweep_current,
304 float inter_sweep_estimate,
305 float intra_sweep_estimate);
306 // Methods called after the end of a sweep to modify the
307 // statistics for the sweep.
308 void end_sweep_dict_census(double splitSurplusPercent);
309 // Return the largest free chunk in the tree.
310 Chunk* find_largest_dict() const;
311 // Accessors for statistics
312 void set_tree_surplus(double splitSurplusPercent);
313 void set_tree_hints(void);
314 // Reset statistics for all the lists in the tree.
315 void clear_tree_census(void);
316 // Print the statistcis for all the lists in the tree. Also may
317 // print out summaries.
318 void print_dict_census(void) const;
319 void print_free_lists(outputStream* st) const;
321 // For debugging. Returns the sum of the _returned_bytes for
322 // all lists in the tree.
323 size_t sum_dict_returned_bytes() PRODUCT_RETURN0;
324 // Sets the _returned_bytes for all the lists in the tree to zero.
325 void initialize_dict_returned_bytes() PRODUCT_RETURN;
326 // For debugging. Return the total number of chunks in the dictionary.
327 size_t total_count() PRODUCT_RETURN0;
329 void report_statistics() const;
331 void verify() const;
332 };
334 #endif // SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP