Mercurial > hg > truffle

comparison src/share/vm/memory/binaryTreeDictionary.hpp @ 6885:685df3c6f84b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
7045397: NPG: Add freelists to class loader arenas. Reviewed-by: coleenp, stefank, jprovino, ohair
author jmasa
date Tue, 18 Sep 2012 23:35:42 -0700
parents da91efe96a93
children 476718ea6759
comparison
equal deleted inserted replaced
6877:d0e7716b179e 6885:685df3c6f84b
35 */ 35 */
36 36
37 // A TreeList is a FreeList which can be used to maintain a 37 // A TreeList is a FreeList which can be used to maintain a
38 // binary tree of free lists. 38 // binary tree of free lists.
39 39
40 template <class Chunk> class TreeChunk; 40 template <class Chunk_t, template <class> class FreeList_t> class TreeChunk;
41 template <class Chunk> class BinaryTreeDictionary; 41 template <class Chunk_t, template <class> class FreeList_t> class BinaryTreeDictionary;
42 template <class Chunk> class AscendTreeCensusClosure; 42 template <class Chunk_t, template <class> class FreeList_t> class AscendTreeCensusClosure;
43 template <class Chunk> class DescendTreeCensusClosure; 43 template <class Chunk_t, template <class> class FreeList_t> class DescendTreeCensusClosure;
44 template <class Chunk> class DescendTreeSearchClosure; 44 template <class Chunk_t, template <class> class FreeList_t> class DescendTreeSearchClosure;
45 45
46 template <class Chunk> 46 template <class Chunk_t, template <class> class FreeList_t>
47 class TreeList: public FreeList<Chunk> { 47 class TreeList : public FreeList_t<Chunk_t> {
48 friend class TreeChunk<Chunk>; 48 friend class TreeChunk<Chunk_t, FreeList_t>;
49 friend class BinaryTreeDictionary<Chunk>; 49 friend class BinaryTreeDictionary<Chunk_t, FreeList_t>;
50 friend class AscendTreeCensusClosure<Chunk>; 50 friend class AscendTreeCensusClosure<Chunk_t, FreeList_t>;
51 friend class DescendTreeCensusClosure<Chunk>; 51 friend class DescendTreeCensusClosure<Chunk_t, FreeList_t>;
52 friend class DescendTreeSearchClosure<Chunk>; 52 friend class DescendTreeSearchClosure<Chunk_t, FreeList_t>;
53 53
54 TreeList<Chunk>* _parent; 54 TreeList<Chunk_t, FreeList_t>* _parent;
55 TreeList<Chunk>* _left; 55 TreeList<Chunk_t, FreeList_t>* _left;
56 TreeList<Chunk>* _right; 56 TreeList<Chunk_t, FreeList_t>* _right;
57 57
58 protected: 58 protected:
59 TreeList<Chunk>* parent() const { return _parent; } 59
60 TreeList<Chunk>* left() const { return _left; } 60 TreeList<Chunk_t, FreeList_t>* parent() const { return _parent; }
61 TreeList<Chunk>* right() const { return _right; } 61 TreeList<Chunk_t, FreeList_t>* left() const { return _left; }
62 62 TreeList<Chunk_t, FreeList_t>* right() const { return _right; }
63 // Explicitly import these names into our namespace to fix name lookup with templates 63
64 using FreeList<Chunk>::head; 64 // Wrapper on call to base class, to get the template to compile.
65 using FreeList<Chunk>::set_head; 65 Chunk_t* head() const { return FreeList_t<Chunk_t>::head(); }
66 66 Chunk_t* tail() const { return FreeList_t<Chunk_t>::tail(); }
67 using FreeList<Chunk>::tail; 67 void set_head(Chunk_t* head) { FreeList_t<Chunk_t>::set_head(head); }
68 using FreeList<Chunk>::set_tail; 68 void set_tail(Chunk_t* tail) { FreeList_t<Chunk_t>::set_tail(tail); }
69 using FreeList<Chunk>::link_tail; 69
70 70 size_t size() const { return FreeList_t<Chunk_t>::size(); }
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;
75 71
76 // Accessors for links in tree. 72 // Accessors for links in tree.
77 73
78 void set_left(TreeList<Chunk>* tl) { 74 void set_left(TreeList<Chunk_t, FreeList_t>* tl) {
79 _left = tl; 75 _left = tl;
80 if (tl != NULL) 76 if (tl != NULL)
81 tl->set_parent(this); 77 tl->set_parent(this);
82 } 78 }
83 void set_right(TreeList<Chunk>* tl) { 79 void set_right(TreeList<Chunk_t, FreeList_t>* tl) {
84 _right = tl; 80 _right = tl;
85 if (tl != NULL) 81 if (tl != NULL)
86 tl->set_parent(this); 82 tl->set_parent(this);
87 } 83 }
88 void set_parent(TreeList<Chunk>* tl) { _parent = tl; } 84 void set_parent(TreeList<Chunk_t, FreeList_t>* tl) { _parent = tl; }
89 85
90 void clearLeft() { _left = NULL; } 86 void clear_left() { _left = NULL; }
91 void clear_right() { _right = NULL; } 87 void clear_right() { _right = NULL; }
92 void clear_parent() { _parent = NULL; } 88 void clear_parent() { _parent = NULL; }
93 void initialize() { clearLeft(); clear_right(), clear_parent(); } 89 void initialize() { clear_left(); clear_right(), clear_parent(); FreeList_t<Chunk_t>::initialize(); }
94 90
95 // For constructing a TreeList from a Tree chunk or 91 // For constructing a TreeList from a Tree chunk or
96 // address and size. 92 // address and size.
97 static TreeList<Chunk>* as_TreeList(TreeChunk<Chunk>* tc); 93 TreeList();
98 static TreeList<Chunk>* as_TreeList(HeapWord* addr, size_t size); 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);
99 97
100 // Returns the head of the free list as a pointer to a TreeChunk. 98 // Returns the head of the free list as a pointer to a TreeChunk.
101 TreeChunk<Chunk>* head_as_TreeChunk(); 99 TreeChunk<Chunk_t, FreeList_t>* head_as_TreeChunk();
102 100
103 // Returns the first available chunk in the free list as a pointer 101 // Returns the first available chunk in the free list as a pointer
104 // to a TreeChunk. 102 // to a TreeChunk.
105 TreeChunk<Chunk>* first_available(); 103 TreeChunk<Chunk_t, FreeList_t>* first_available();
106 104
107 // Returns the block with the largest heap address amongst 105 // Returns the block with the largest heap address amongst
108 // those in the list for this size; potentially slow and expensive, 106 // those in the list for this size; potentially slow and expensive,
109 // use with caution! 107 // use with caution!
110 TreeChunk<Chunk>* largest_address(); 108 TreeChunk<Chunk_t, FreeList_t>* largest_address();
109
110 TreeList<Chunk_t, FreeList_t>* get_better_list(
111 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary);
111 112
112 // remove_chunk_replace_if_needed() removes the given "tc" from the TreeList. 113 // 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 // 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 // TreeList that is the node in the tree. remove_chunk_replace_if_needed()
115 // returns the possibly replaced TreeList* for the node in 116 // returns the possibly replaced TreeList* for the node in
116 // the tree. It also updates the parent of the original 117 // the tree. It also updates the parent of the original
117 // node to point to the new node. 118 // node to point to the new node.
118 TreeList<Chunk>* remove_chunk_replace_if_needed(TreeChunk<Chunk>* tc); 119 TreeList<Chunk_t, FreeList_t>* remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc);
119 // See FreeList. 120 // See FreeList.
120 void return_chunk_at_head(TreeChunk<Chunk>* tc); 121 void return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* tc);
121 void return_chunk_at_tail(TreeChunk<Chunk>* tc); 122 void return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* tc);
122 }; 123 };
123 124
124 // A TreeChunk is a subclass of a Chunk that additionally 125 // A TreeChunk is a subclass of a Chunk that additionally
125 // maintains a pointer to the free list on which it is currently 126 // maintains a pointer to the free list on which it is currently
126 // linked. 127 // linked.
132 // the first chunk in the list is distinguished in this fashion 133 // 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 // (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 // 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. 136 // it is the last chunk on the free list.
136 137
137 template <class Chunk> 138 template <class Chunk_t, template <class> class FreeList_t>
138 class TreeChunk : public Chunk { 139 class TreeChunk : public Chunk_t {
139 friend class TreeList<Chunk>; 140 friend class TreeList<Chunk_t, FreeList_t>;
140 TreeList<Chunk>* _list; 141 TreeList<Chunk_t, FreeList_t>* _list;
141 TreeList<Chunk> _embedded_list; // if non-null, this chunk is on _list 142 TreeList<Chunk_t, FreeList_t> _embedded_list; // if non-null, this chunk is on _list
143
144 static size_t _min_tree_chunk_size;
145
142 protected: 146 protected:
143 TreeList<Chunk>* embedded_list() const { return (TreeList<Chunk>*) &_embedded_list; } 147 TreeList<Chunk_t, FreeList_t>* embedded_list() const { return (TreeList<Chunk_t, FreeList_t>*) &_embedded_list; }
144 void set_embedded_list(TreeList<Chunk>* v) { _embedded_list = *v; } 148 void set_embedded_list(TreeList<Chunk_t, FreeList_t>* v) { _embedded_list = *v; }
145 public: 149 public:
146 TreeList<Chunk>* list() { return _list; } 150 TreeList<Chunk_t, FreeList_t>* list() { return _list; }
147 void set_list(TreeList<Chunk>* v) { _list = v; } 151 void set_list(TreeList<Chunk_t, FreeList_t>* v) { _list = v; }
148 static TreeChunk<Chunk>* as_TreeChunk(Chunk* fc); 152 static TreeChunk<Chunk_t, FreeList_t>* as_TreeChunk(Chunk_t* fc);
149 // Initialize fields in a TreeChunk that should be 153 // Initialize fields in a TreeChunk that should be
150 // initialized when the TreeChunk is being added to 154 // initialized when the TreeChunk is being added to
151 // a free list in the tree. 155 // a free list in the tree.
152 void initialize() { embedded_list()->initialize(); } 156 void initialize() { embedded_list()->initialize(); }
153 157
154 Chunk* next() const { return Chunk::next(); } 158 Chunk_t* next() const { return Chunk_t::next(); }
155 Chunk* prev() const { return Chunk::prev(); } 159 Chunk_t* prev() const { return Chunk_t::prev(); }
156 size_t size() const volatile { return Chunk::size(); } 160 size_t size() const volatile { return Chunk_t::size(); }
161
162 static size_t min_size() {
163 return _min_tree_chunk_size;
164 }
157 165
158 // debugging 166 // debugging
159 void verify_tree_chunk_list() const; 167 void verify_tree_chunk_list() const;
168 void assert_is_mangled() const;
160 }; 169 };
161 170
162 171
163 template <class Chunk> 172 template <class Chunk_t, template <class> class FreeList_t>
164 class BinaryTreeDictionary: public FreeBlockDictionary<Chunk> { 173 class BinaryTreeDictionary: public FreeBlockDictionary<Chunk_t> {
165 friend class VMStructs; 174 friend class VMStructs;
166 bool _splay;
167 bool _adaptive_freelists;
168 size_t _total_size; 175 size_t _total_size;
169 size_t _total_free_blocks; 176 size_t _total_free_blocks;
170 TreeList<Chunk>* _root; 177 TreeList<Chunk_t, FreeList_t>* _root;
171 178
172 // private accessors 179 // 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; } 180 void set_total_size(size_t v) { _total_size = v; }
176 virtual void inc_total_size(size_t v); 181 virtual void inc_total_size(size_t v);
177 virtual void dec_total_size(size_t v); 182 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; } 183 void set_total_free_blocks(size_t v) { _total_free_blocks = v; }
180 TreeList<Chunk>* root() const { return _root; } 184 TreeList<Chunk_t, FreeList_t>* root() const { return _root; }
181 void set_root(TreeList<Chunk>* v) { _root = v; } 185 void set_root(TreeList<Chunk_t, FreeList_t>* v) { _root = v; }
182 bool adaptive_freelists() { return _adaptive_freelists; }
183 186
184 // This field is added and can be set to point to the 187 // This field is added and can be set to point to the
185 // the Mutex used to synchronize access to the 188 // the Mutex used to synchronize access to the
186 // dictionary so that assertion checking can be done. 189 // dictionary so that assertion checking can be done.
187 // For example it is set to point to _parDictionaryAllocLock. 190 // For example it is set to point to _parDictionaryAllocLock.
189 192
190 // Remove a chunk of size "size" or larger from the tree and 193 // Remove a chunk of size "size" or larger from the tree and
191 // return it. If the chunk 194 // return it. If the chunk
192 // is the last chunk of that size, remove the node for that size 195 // is the last chunk of that size, remove the node for that size
193 // from the tree. 196 // from the tree.
194 TreeChunk<Chunk>* get_chunk_from_tree(size_t size, enum FreeBlockDictionary<Chunk>::Dither dither, bool splay); 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:
207
195 // Return a list of the specified size or NULL from the tree. 208 // Return a list of the specified size or NULL from the tree.
196 // The list is not removed from the tree. 209 // The list is not removed from the tree.
197 TreeList<Chunk>* find_list (size_t size) const; 210 TreeList<Chunk_t, FreeList_t>* 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:
208
209 static const size_t min_tree_chunk_size = sizeof(TreeChunk<Chunk>)/HeapWordSize;
210 211
211 void verify_tree() const; 212 void verify_tree() const;
212 // verify that the given chunk is in the tree. 213 // verify that the given chunk is in the tree.
213 bool verify_chunk_in_free_list(Chunk* tc) const; 214 bool verify_chunk_in_free_list(Chunk_t* tc) const;
214 private: 215 private:
215 void verify_tree_helper(TreeList<Chunk>* tl) const; 216 void verify_tree_helper(TreeList<Chunk_t, FreeList_t>* tl) const;
216 static size_t verify_prev_free_ptrs(TreeList<Chunk>* tl); 217 static size_t verify_prev_free_ptrs(TreeList<Chunk_t, FreeList_t>* tl);
217 218
218 // Returns the total number of chunks in the list. 219 // Returns the total number of chunks in the list.
219 size_t total_list_length(TreeList<Chunk>* tl) const; 220 size_t total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const;
220 // Returns the total number of words in the chunks in the tree 221 // Returns the total number of words in the chunks in the tree
221 // starting at "tl". 222 // starting at "tl".
222 size_t total_size_in_tree(TreeList<Chunk>* tl) const; 223 size_t total_size_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const;
223 // Returns the sum of the square of the size of each block 224 // Returns the sum of the square of the size of each block
224 // in the tree starting at "tl". 225 // in the tree starting at "tl".
225 double sum_of_squared_block_sizes(TreeList<Chunk>* const tl) const; 226 double sum_of_squared_block_sizes(TreeList<Chunk_t, FreeList_t>* const tl) const;
226 // Returns the total number of free blocks in the tree starting 227 // Returns the total number of free blocks in the tree starting
227 // at "tl". 228 // at "tl".
228 size_t total_free_blocks_in_tree(TreeList<Chunk>* tl) const; 229 size_t total_free_blocks_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const;
229 size_t num_free_blocks() const; 230 size_t num_free_blocks() const;
230 size_t treeHeight() const; 231 size_t tree_height() const;
231 size_t tree_height_helper(TreeList<Chunk>* tl) const; 232 size_t tree_height_helper(TreeList<Chunk_t, FreeList_t>* tl) const;
232 size_t total_nodes_in_tree(TreeList<Chunk>* tl) const; 233 size_t total_nodes_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const;
233 size_t total_nodes_helper(TreeList<Chunk>* tl) const; 234 size_t total_nodes_helper(TreeList<Chunk_t, FreeList_t>* tl) const;
234 235
235 public: 236 public:
236 // Constructor 237 // Constructor
237 BinaryTreeDictionary(bool adaptive_freelists, bool splay = false); 238 BinaryTreeDictionary() :
238 BinaryTreeDictionary(MemRegion mr, bool adaptive_freelists, bool splay = false); 239 _total_size(0), _total_free_blocks(0), _root(0) {}
240
241 BinaryTreeDictionary(MemRegion mr);
239 242
240 // Public accessors 243 // Public accessors
241 size_t total_size() const { return _total_size; } 244 size_t total_size() const { return _total_size; }
245 size_t total_free_blocks() const { return _total_free_blocks; }
242 246
243 // Reset the dictionary to the initial conditions with 247 // Reset the dictionary to the initial conditions with
244 // a single free chunk. 248 // a single free chunk.
245 void reset(MemRegion mr); 249 void reset(MemRegion mr);
246 void reset(HeapWord* addr, size_t size); 250 void reset(HeapWord* addr, size_t size);
247 // Reset the dictionary to be empty. 251 // Reset the dictionary to be empty.
248 void reset(); 252 void reset();
249 253
250 // Return a chunk of size "size" or greater from 254 // Return a chunk of size "size" or greater from
251 // the tree. 255 // the tree.
252 // want a better dynamic splay strategy for the future. 256 Chunk_t* get_chunk(size_t size, enum FreeBlockDictionary<Chunk_t>::Dither dither) {
253 Chunk* get_chunk(size_t size, enum FreeBlockDictionary<Chunk>::Dither dither) { 257 FreeBlockDictionary<Chunk_t>::verify_par_locked();
254 FreeBlockDictionary<Chunk>::verify_par_locked(); 258 Chunk_t* res = get_chunk_from_tree(size, dither);
255 Chunk* res = get_chunk_from_tree(size, dither, splay());
256 assert(res == NULL || res->is_free(), 259 assert(res == NULL || res->is_free(),
257 "Should be returning a free chunk"); 260 "Should be returning a free chunk");
261 assert(dither != FreeBlockDictionary<Chunk_t>::exactly ||
262 res->size() == size, "Not correct size");
258 return res; 263 return res;
259 } 264 }
260 265
261 void return_chunk(Chunk* chunk) { 266 void return_chunk(Chunk_t* chunk) {
262 FreeBlockDictionary<Chunk>::verify_par_locked(); 267 FreeBlockDictionary<Chunk_t>::verify_par_locked();
263 insert_chunk_in_tree(chunk); 268 insert_chunk_in_tree(chunk);
264 } 269 }
265 270
266 void remove_chunk(Chunk* chunk) { 271 void remove_chunk(Chunk_t* chunk) {
267 FreeBlockDictionary<Chunk>::verify_par_locked(); 272 FreeBlockDictionary<Chunk_t>::verify_par_locked();
268 remove_chunk_from_tree((TreeChunk<Chunk>*)chunk); 273 remove_chunk_from_tree((TreeChunk<Chunk_t, FreeList_t>*)chunk);
269 assert(chunk->is_free(), "Should still be a free chunk"); 274 assert(chunk->is_free(), "Should still be a free chunk");
270 } 275 }
271 276
272 size_t max_chunk_size() const; 277 size_t max_chunk_size() const;
273 size_t total_chunk_size(debug_only(const Mutex* lock)) const { 278 size_t total_chunk_size(debug_only(const Mutex* lock)) const {
279 ) 284 )
280 return total_size(); 285 return total_size();
281 } 286 }
282 287
283 size_t min_size() const { 288 size_t min_size() const {
284 return min_tree_chunk_size; 289 return TreeChunk<Chunk_t, FreeList_t>::min_size();
285 } 290 }
286 291
287 double sum_of_squared_block_sizes() const { 292 double sum_of_squared_block_sizes() const {
288 return sum_of_squared_block_sizes(root()); 293 return sum_of_squared_block_sizes(root());
289 } 294 }
290 295
291 Chunk* find_chunk_ends_at(HeapWord* target) const; 296 Chunk_t* find_chunk_ends_at(HeapWord* target) const;
292 297
293 // Find the list with size "size" in the binary tree and update 298 // Find the list with size "size" in the binary tree and update
294 // the statistics in the list according to "split" (chunk was 299 // the statistics in the list according to "split" (chunk was
295 // split or coalesce) and "birth" (chunk was added or removed). 300 // split or coalesce) and "birth" (chunk was added or removed).
296 void dict_census_udpate(size_t size, bool split, bool birth); 301 void dict_census_update(size_t size, bool split, bool birth);
297 // Return true if the dictionary is overpopulated (more chunks of 302 // Return true if the dictionary is overpopulated (more chunks of
298 // this size than desired) for size "size". 303 // this size than desired) for size "size".
299 bool coal_dict_over_populated(size_t size); 304 bool coal_dict_over_populated(size_t size);
300 // Methods called at the beginning of a sweep to prepare the 305 // Methods called at the beginning of a sweep to prepare the
301 // statistics for the sweep. 306 // statistics for the sweep.
305 float intra_sweep_estimate); 310 float intra_sweep_estimate);
306 // Methods called after the end of a sweep to modify the 311 // Methods called after the end of a sweep to modify the
307 // statistics for the sweep. 312 // statistics for the sweep.
308 void end_sweep_dict_census(double splitSurplusPercent); 313 void end_sweep_dict_census(double splitSurplusPercent);
309 // Return the largest free chunk in the tree. 314 // Return the largest free chunk in the tree.
310 Chunk* find_largest_dict() const; 315 Chunk_t* find_largest_dict() const;
311 // Accessors for statistics 316 // Accessors for statistics
312 void set_tree_surplus(double splitSurplusPercent); 317 void set_tree_surplus(double splitSurplusPercent);
313 void set_tree_hints(void); 318 void set_tree_hints(void);
314 // Reset statistics for all the lists in the tree. 319 // Reset statistics for all the lists in the tree.
315 void clear_tree_census(void); 320 void clear_tree_census(void);