222 assert(this == retTL->parent()->right(), "Parent is incorrect");
223 retTL->parent()->set_right(retTL);
224 }
225 }
226 // Fix the children's parent pointers to point to the
227 // new list.
228 assert(right() == retTL->right(), "Should have been copied");
229 if (retTL->right() != NULL) {
230 retTL->right()->set_parent(retTL);
231 }
232 assert(left() == retTL->left(), "Should have been copied");
233 if (retTL->left() != NULL) {
234 retTL->left()->set_parent(retTL);
235 }
236 retTL->link_head(nextTC);
237 assert(nextTC->is_free(), "Should be a free chunk");
238 }
239 } else {
240 if (nextTC == NULL) {
241 // Removing chunk at tail of list
242 link_tail(prevFC);
243 }
244 // Chunk is interior to the list
245 prevFC->link_after(nextTC);
246 }
247
248 // Below this point the embeded TreeList<Chunk_t, FreeList_t> being used for the
249 // tree node may have changed. Don't use "this"
250 // TreeList<Chunk_t, FreeList_t>*.
251 // chunk should still be a free chunk (bit set in _prev)
252 assert(!retTL->head() || retTL->size() == retTL->head()->size(),
253 "Wrong sized chunk in list");
254 debug_only(
255 tc->link_prev(NULL);
256 tc->link_next(NULL);
257 tc->set_list(NULL);
258 bool prev_found = false;
259 bool next_found = false;
260 for (Chunk_t* curFC = retTL->head();
261 curFC != NULL; curFC = curFC->next()) {
262 assert(curFC != tc, "Chunk is still in list");
279 assert(tc->is_free(), "Should still be a free chunk");
280 assert(retTL->head() == NULL || retTL->head()->prev() == NULL,
281 "list invariant");
282 assert(retTL->tail() == NULL || retTL->tail()->next() == NULL,
283 "list invariant");
284 return retTL;
285 }
286
287 template <class Chunk_t, template <class> class FreeList_t>
288 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* chunk) {
289 assert(chunk != NULL, "returning NULL chunk");
290 assert(chunk->list() == this, "list should be set for chunk");
291 assert(tail() != NULL, "The tree list is embedded in the first chunk");
292 // which means that the list can never be empty.
293 assert(!verify_chunk_in_free_list(chunk), "Double entry");
294 assert(head() == NULL || head()->prev() == NULL, "list invariant");
295 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
296
297 Chunk_t* fc = tail();
298 fc->link_after(chunk);
299 link_tail(chunk);
300
301 assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list");
302 FreeList_t<Chunk_t>::increment_count();
303 debug_only(increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));)
304 assert(head() == NULL || head()->prev() == NULL, "list invariant");
305 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
306 }
307
308 // Add this chunk at the head of the list. "At the head of the list"
309 // is defined to be after the chunk pointer to by head(). This is
310 // because the TreeList<Chunk_t, FreeList_t> is embedded in the first TreeChunk<Chunk_t, FreeList_t> in the
311 // list. See the definition of TreeChunk<Chunk_t, FreeList_t>.
312 template <class Chunk_t, template <class> class FreeList_t>
313 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* chunk) {
314 assert(chunk->list() == this, "list should be set for chunk");
315 assert(head() != NULL, "The tree list is embedded in the first chunk");
316 assert(chunk != NULL, "returning NULL chunk");
317 assert(!verify_chunk_in_free_list(chunk), "Double entry");
318 assert(head() == NULL || head()->prev() == NULL, "list invariant");
319 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
320
321 Chunk_t* fc = head()->next();
322 if (fc != NULL) {
323 chunk->link_after(fc);
324 } else {
325 assert(tail() == NULL, "List is inconsistent");
326 link_tail(chunk);
327 }
328 head()->link_after(chunk);
329 assert(!head() || size() == head()->size(), "Wrong sized chunk in list");
330 FreeList_t<Chunk_t>::increment_count();
331 debug_only(increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));)
332 assert(head() == NULL || head()->prev() == NULL, "list invariant");
333 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
334 }
335
336 template <class Chunk_t, template <class> class FreeList_t>
337 void TreeChunk<Chunk_t, FreeList_t>::assert_is_mangled() const {
338 assert((ZapUnusedHeapArea &&
339 SpaceMangler::is_mangled((HeapWord*) Chunk_t::size_addr()) &&
340 SpaceMangler::is_mangled((HeapWord*) Chunk_t::prev_addr()) &&
341 SpaceMangler::is_mangled((HeapWord*) Chunk_t::next_addr())) ||
342 (size() == 0 && prev() == NULL && next() == NULL),
343 "Space should be clear or mangled");
344 }
345
346 template <class Chunk_t, template <class> class FreeList_t>
923 // Closures for walking the binary tree.
924 // do_list() walks the free list in a node applying the closure
925 // to each free chunk in the list
926 // do_tree() walks the nodes in the binary tree applying do_list()
927 // to each list at each node.
928
929 template <class Chunk_t, template <class> class FreeList_t>
930 class TreeCensusClosure : public StackObj {
931 protected:
932 virtual void do_list(FreeList_t<Chunk_t>* fl) = 0;
933 public:
934 virtual void do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0;
935 };
936
937 template <class Chunk_t, template <class> class FreeList_t>
938 class AscendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> {
939 public:
940 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
941 if (tl != NULL) {
942 do_tree(tl->left());
943 do_list(tl);
944 do_tree(tl->right());
945 }
946 }
947 };
948
949 template <class Chunk_t, template <class> class FreeList_t>
950 class DescendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> {
951 public:
952 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
953 if (tl != NULL) {
954 do_tree(tl->right());
955 do_list(tl);
956 do_tree(tl->left());
957 }
958 }
959 };
960
961 // For each list in the tree, calculate the desired, desired
962 // coalesce, count before sweep, and surplus before sweep.
963 template <class Chunk_t, template <class> class FreeList_t>
964 class BeginSweepClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
965 double _percentage;
966 float _inter_sweep_current;
967 float _inter_sweep_estimate;
968 float _intra_sweep_estimate;
969
970 public:
971 BeginSweepClosure(double p, float inter_sweep_current,
972 float inter_sweep_estimate,
973 float intra_sweep_estimate) :
974 _percentage(p),
975 _inter_sweep_current(inter_sweep_current),
1005 template <class Chunk_t, template <class> class FreeList_t>
1006 class AscendTreeSearchClosure : public TreeSearchClosure<Chunk_t> {
1007 public:
1008 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
1009 if (tl != NULL) {
1010 if (do_tree(tl->left())) return true;
1011 if (do_list(tl)) return true;
1012 if (do_tree(tl->right())) return true;
1013 }
1014 return false;
1015 }
1016 };
1017 #endif
1018
1019 template <class Chunk_t, template <class> class FreeList_t>
1020 class DescendTreeSearchClosure : public TreeSearchClosure<Chunk_t, FreeList_t> {
1021 public:
1022 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
1023 if (tl != NULL) {
1024 if (do_tree(tl->right())) return true;
1025 if (do_list(tl)) return true;
1026 if (do_tree(tl->left())) return true;
1027 }
1028 return false;
1029 }
1030 };
1031
1032 // Searches the tree for a chunk that ends at the
1033 // specified address.
1034 template <class Chunk_t, template <class> class FreeList_t>
1035 class EndTreeSearchClosure : public DescendTreeSearchClosure<Chunk_t, FreeList_t> {
1036 HeapWord* _target;
1037 Chunk_t* _found;
1038
1039 public:
1040 EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {}
1041 bool do_list(FreeList_t<Chunk_t>* fl) {
1042 Chunk_t* item = fl->head();
1043 while (item != NULL) {
1044 if (item->end() == (uintptr_t*) _target) {
1045 _found = item;
|
222 assert(this == retTL->parent()->right(), "Parent is incorrect");
223 retTL->parent()->set_right(retTL);
224 }
225 }
226 // Fix the children's parent pointers to point to the
227 // new list.
228 assert(right() == retTL->right(), "Should have been copied");
229 if (retTL->right() != NULL) {
230 retTL->right()->set_parent(retTL);
231 }
232 assert(left() == retTL->left(), "Should have been copied");
233 if (retTL->left() != NULL) {
234 retTL->left()->set_parent(retTL);
235 }
236 retTL->link_head(nextTC);
237 assert(nextTC->is_free(), "Should be a free chunk");
238 }
239 } else {
240 if (nextTC == NULL) {
241 // Removing chunk at tail of list
242 this->link_tail(prevFC);
243 }
244 // Chunk is interior to the list
245 prevFC->link_after(nextTC);
246 }
247
248 // Below this point the embeded TreeList<Chunk_t, FreeList_t> being used for the
249 // tree node may have changed. Don't use "this"
250 // TreeList<Chunk_t, FreeList_t>*.
251 // chunk should still be a free chunk (bit set in _prev)
252 assert(!retTL->head() || retTL->size() == retTL->head()->size(),
253 "Wrong sized chunk in list");
254 debug_only(
255 tc->link_prev(NULL);
256 tc->link_next(NULL);
257 tc->set_list(NULL);
258 bool prev_found = false;
259 bool next_found = false;
260 for (Chunk_t* curFC = retTL->head();
261 curFC != NULL; curFC = curFC->next()) {
262 assert(curFC != tc, "Chunk is still in list");
279 assert(tc->is_free(), "Should still be a free chunk");
280 assert(retTL->head() == NULL || retTL->head()->prev() == NULL,
281 "list invariant");
282 assert(retTL->tail() == NULL || retTL->tail()->next() == NULL,
283 "list invariant");
284 return retTL;
285 }
286
287 template <class Chunk_t, template <class> class FreeList_t>
288 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* chunk) {
289 assert(chunk != NULL, "returning NULL chunk");
290 assert(chunk->list() == this, "list should be set for chunk");
291 assert(tail() != NULL, "The tree list is embedded in the first chunk");
292 // which means that the list can never be empty.
293 assert(!verify_chunk_in_free_list(chunk), "Double entry");
294 assert(head() == NULL || head()->prev() == NULL, "list invariant");
295 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
296
297 Chunk_t* fc = tail();
298 fc->link_after(chunk);
299 this->link_tail(chunk);
300
301 assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list");
302 FreeList_t<Chunk_t>::increment_count();
303 debug_only(increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));)
304 assert(head() == NULL || head()->prev() == NULL, "list invariant");
305 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
306 }
307
308 // Add this chunk at the head of the list. "At the head of the list"
309 // is defined to be after the chunk pointer to by head(). This is
310 // because the TreeList<Chunk_t, FreeList_t> is embedded in the first TreeChunk<Chunk_t, FreeList_t> in the
311 // list. See the definition of TreeChunk<Chunk_t, FreeList_t>.
312 template <class Chunk_t, template <class> class FreeList_t>
313 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* chunk) {
314 assert(chunk->list() == this, "list should be set for chunk");
315 assert(head() != NULL, "The tree list is embedded in the first chunk");
316 assert(chunk != NULL, "returning NULL chunk");
317 assert(!verify_chunk_in_free_list(chunk), "Double entry");
318 assert(head() == NULL || head()->prev() == NULL, "list invariant");
319 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
320
321 Chunk_t* fc = head()->next();
322 if (fc != NULL) {
323 chunk->link_after(fc);
324 } else {
325 assert(tail() == NULL, "List is inconsistent");
326 this->link_tail(chunk);
327 }
328 head()->link_after(chunk);
329 assert(!head() || size() == head()->size(), "Wrong sized chunk in list");
330 FreeList_t<Chunk_t>::increment_count();
331 debug_only(increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));)
332 assert(head() == NULL || head()->prev() == NULL, "list invariant");
333 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
334 }
335
336 template <class Chunk_t, template <class> class FreeList_t>
337 void TreeChunk<Chunk_t, FreeList_t>::assert_is_mangled() const {
338 assert((ZapUnusedHeapArea &&
339 SpaceMangler::is_mangled((HeapWord*) Chunk_t::size_addr()) &&
340 SpaceMangler::is_mangled((HeapWord*) Chunk_t::prev_addr()) &&
341 SpaceMangler::is_mangled((HeapWord*) Chunk_t::next_addr())) ||
342 (size() == 0 && prev() == NULL && next() == NULL),
343 "Space should be clear or mangled");
344 }
345
346 template <class Chunk_t, template <class> class FreeList_t>
923 // Closures for walking the binary tree.
924 // do_list() walks the free list in a node applying the closure
925 // to each free chunk in the list
926 // do_tree() walks the nodes in the binary tree applying do_list()
927 // to each list at each node.
928
929 template <class Chunk_t, template <class> class FreeList_t>
930 class TreeCensusClosure : public StackObj {
931 protected:
932 virtual void do_list(FreeList_t<Chunk_t>* fl) = 0;
933 public:
934 virtual void do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0;
935 };
936
937 template <class Chunk_t, template <class> class FreeList_t>
938 class AscendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> {
939 public:
940 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
941 if (tl != NULL) {
942 do_tree(tl->left());
943 this->do_list(tl);
944 do_tree(tl->right());
945 }
946 }
947 };
948
949 template <class Chunk_t, template <class> class FreeList_t>
950 class DescendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> {
951 public:
952 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
953 if (tl != NULL) {
954 do_tree(tl->right());
955 this->do_list(tl);
956 do_tree(tl->left());
957 }
958 }
959 };
960
961 // For each list in the tree, calculate the desired, desired
962 // coalesce, count before sweep, and surplus before sweep.
963 template <class Chunk_t, template <class> class FreeList_t>
964 class BeginSweepClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
965 double _percentage;
966 float _inter_sweep_current;
967 float _inter_sweep_estimate;
968 float _intra_sweep_estimate;
969
970 public:
971 BeginSweepClosure(double p, float inter_sweep_current,
972 float inter_sweep_estimate,
973 float intra_sweep_estimate) :
974 _percentage(p),
975 _inter_sweep_current(inter_sweep_current),
1005 template <class Chunk_t, template <class> class FreeList_t>
1006 class AscendTreeSearchClosure : public TreeSearchClosure<Chunk_t> {
1007 public:
1008 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
1009 if (tl != NULL) {
1010 if (do_tree(tl->left())) return true;
1011 if (do_list(tl)) return true;
1012 if (do_tree(tl->right())) return true;
1013 }
1014 return false;
1015 }
1016 };
1017 #endif
1018
1019 template <class Chunk_t, template <class> class FreeList_t>
1020 class DescendTreeSearchClosure : public TreeSearchClosure<Chunk_t, FreeList_t> {
1021 public:
1022 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
1023 if (tl != NULL) {
1024 if (do_tree(tl->right())) return true;
1025 if (this->do_list(tl)) return true;
1026 if (do_tree(tl->left())) return true;
1027 }
1028 return false;
1029 }
1030 };
1031
1032 // Searches the tree for a chunk that ends at the
1033 // specified address.
1034 template <class Chunk_t, template <class> class FreeList_t>
1035 class EndTreeSearchClosure : public DescendTreeSearchClosure<Chunk_t, FreeList_t> {
1036 HeapWord* _target;
1037 Chunk_t* _found;
1038
1039 public:
1040 EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {}
1041 bool do_list(FreeList_t<Chunk_t>* fl) {
1042 Chunk_t* item = fl->head();
1043 while (item != NULL) {
1044 if (item->end() == (uintptr_t*) _target) {
1045 _found = item;
|