20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25 #ifndef SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP 26 #define SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP 27 28 #include "memory/freeBlockDictionary.hpp" 29 #include "memory/freeList.hpp" 30 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 */ 36 37 // A TreeList is a FreeList which can be used to maintain a 38 // binary tree of free lists. 39 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; 45 46 class FreeChunk; 47 template <class> class AdaptiveFreeList; 48 typedef BinaryTreeDictionary<FreeChunk, AdaptiveFreeList> AFLBinaryTreeDictionary; 49 50 template <class Chunk_t, template <class> class FreeList_t> 51 class TreeList : public FreeList_t<Chunk_t> { 52 friend class TreeChunk<Chunk_t, FreeList_t>; 53 friend class BinaryTreeDictionary<Chunk_t, FreeList_t>; 54 friend class AscendTreeCensusClosure<Chunk_t, FreeList_t>; 55 friend class DescendTreeCensusClosure<Chunk_t, FreeList_t>; 56 friend class DescendTreeSearchClosure<Chunk_t, FreeList_t>; 57 58 TreeList<Chunk_t, FreeList_t>* _parent; 59 TreeList<Chunk_t, FreeList_t>* _left; 60 TreeList<Chunk_t, FreeList_t>* _right; 61 62 protected: 63 64 TreeList<Chunk_t, FreeList_t>* parent() const { return _parent; } 65 TreeList<Chunk_t, FreeList_t>* left() const { return _left; } 66 TreeList<Chunk_t, FreeList_t>* right() const { return _right; } 67 68 // Wrapper on call to base class, to get the template to compile. 69 Chunk_t* head() const { return FreeList_t<Chunk_t>::head(); } 70 Chunk_t* tail() const { return FreeList_t<Chunk_t>::tail(); } 71 void set_head(Chunk_t* head) { FreeList_t<Chunk_t>::set_head(head); } 72 void set_tail(Chunk_t* tail) { FreeList_t<Chunk_t>::set_tail(tail); } 73 74 size_t size() const { return FreeList_t<Chunk_t>::size(); } 75 76 // Accessors for links in tree. 77 78 void set_left(TreeList<Chunk_t, FreeList_t>* tl) { 79 _left = tl; 80 if (tl != NULL) 81 tl->set_parent(this); 82 } 83 void set_right(TreeList<Chunk_t, FreeList_t>* tl) { 84 _right = tl; 85 if (tl != NULL) 86 tl->set_parent(this); 87 } 88 void set_parent(TreeList<Chunk_t, FreeList_t>* tl) { _parent = tl; } 89 90 void clear_left() { _left = NULL; } 91 void clear_right() { _right = NULL; } 92 void clear_parent() { _parent = NULL; } 93 void initialize() { clear_left(); clear_right(), clear_parent(); FreeList_t<Chunk_t>::initialize(); } 94 95 // For constructing a TreeList from a Tree chunk or 96 // address and size. 97 TreeList(); 98 static TreeList<Chunk_t, FreeList_t>* 99 as_TreeList(TreeChunk<Chunk_t, FreeList_t>* tc); 100 static TreeList<Chunk_t, FreeList_t>* as_TreeList(HeapWord* addr, size_t size); 101 102 // Returns the head of the free list as a pointer to a TreeChunk. 103 TreeChunk<Chunk_t, FreeList_t>* head_as_TreeChunk(); 104 105 // Returns the first available chunk in the free list as a pointer 106 // to a TreeChunk. 107 TreeChunk<Chunk_t, FreeList_t>* first_available(); 108 109 // Returns the block with the largest heap address amongst 110 // those in the list for this size; potentially slow and expensive, 111 // use with caution! 112 TreeChunk<Chunk_t, FreeList_t>* largest_address(); 113 122 // node to point to the new node. 123 TreeList<Chunk_t, FreeList_t>* remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc); 124 // See FreeList. 125 void return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* tc); 126 void return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* tc); 127 }; 128 129 // A TreeChunk is a subclass of a Chunk that additionally 130 // maintains a pointer to the free list on which it is currently 131 // linked. 132 // A TreeChunk is also used as a node in the binary tree. This 133 // allows the binary tree to be maintained without any additional 134 // storage (the free chunks are used). In a binary tree the first 135 // chunk in the free list is also the tree node. Note that the 136 // TreeChunk has an embedded TreeList for this purpose. Because 137 // the first chunk in the list is distinguished in this fashion 138 // (also is the node in the tree), it is the last chunk to be found 139 // on the free list for a node in the tree and is only removed if 140 // it is the last chunk on the free list. 141 142 template <class Chunk_t, template <class> class FreeList_t> 143 class TreeChunk : public Chunk_t { 144 friend class TreeList<Chunk_t, FreeList_t>; 145 TreeList<Chunk_t, FreeList_t>* _list; 146 TreeList<Chunk_t, FreeList_t> _embedded_list; // if non-null, this chunk is on _list 147 148 static size_t _min_tree_chunk_size; 149 150 protected: 151 TreeList<Chunk_t, FreeList_t>* embedded_list() const { return (TreeList<Chunk_t, FreeList_t>*) &_embedded_list; } 152 void set_embedded_list(TreeList<Chunk_t, FreeList_t>* v) { _embedded_list = *v; } 153 public: 154 TreeList<Chunk_t, FreeList_t>* list() { return _list; } 155 void set_list(TreeList<Chunk_t, FreeList_t>* v) { _list = v; } 156 static TreeChunk<Chunk_t, FreeList_t>* as_TreeChunk(Chunk_t* fc); 157 // Initialize fields in a TreeChunk that should be 158 // initialized when the TreeChunk is being added to 159 // a free list in the tree. 160 void initialize() { embedded_list()->initialize(); } 161 162 Chunk_t* next() const { return Chunk_t::next(); } 163 Chunk_t* prev() const { return Chunk_t::prev(); } 164 size_t size() const volatile { return Chunk_t::size(); } 165 166 static size_t min_size() { 167 return _min_tree_chunk_size; 168 } 169 170 // debugging 171 void verify_tree_chunk_list() const; 172 void assert_is_mangled() const; 173 }; 174 175 176 template <class Chunk_t, template <class> class FreeList_t> 177 class BinaryTreeDictionary: public FreeBlockDictionary<Chunk_t> { 178 friend class VMStructs; 179 size_t _total_size; 180 size_t _total_free_blocks; 181 TreeList<Chunk_t, FreeList_t>* _root; 182 183 // private accessors 184 void set_total_size(size_t v) { _total_size = v; } 185 virtual void inc_total_size(size_t v); 186 virtual void dec_total_size(size_t v); 187 void set_total_free_blocks(size_t v) { _total_free_blocks = v; } 188 TreeList<Chunk_t, FreeList_t>* root() const { return _root; } 189 void set_root(TreeList<Chunk_t, FreeList_t>* v) { _root = v; } 190 191 // This field is added and can be set to point to the 192 // the Mutex used to synchronize access to the 193 // dictionary so that assertion checking can be done. 194 // For example it is set to point to _parDictionaryAllocLock. 195 NOT_PRODUCT(Mutex* _lock;) 196 | 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25 #ifndef SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP 26 #define SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP 27 28 #include "memory/freeBlockDictionary.hpp" 29 #include "memory/freeList.hpp" 30 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 */ 36 37 // A TreeList is a FreeList which can be used to maintain a 38 // binary tree of free lists. 39 40 template <class Chunk_t, class FreeList_t> class TreeChunk; 41 template <class Chunk_t, class FreeList_t> class BinaryTreeDictionary; 42 template <class Chunk_t, class FreeList_t> class AscendTreeCensusClosure; 43 template <class Chunk_t, class FreeList_t> class DescendTreeCensusClosure; 44 template <class Chunk_t, class FreeList_t> class DescendTreeSearchClosure; 45 46 class FreeChunk; 47 template <class> class AdaptiveFreeList; 48 typedef BinaryTreeDictionary<FreeChunk, AdaptiveFreeList<FreeChunk> > AFLBinaryTreeDictionary; 49 50 template <class Chunk_t, class FreeList_t> 51 class TreeList : public FreeList_t { 52 friend class TreeChunk<Chunk_t, FreeList_t>; 53 friend class BinaryTreeDictionary<Chunk_t, FreeList_t>; 54 friend class AscendTreeCensusClosure<Chunk_t, FreeList_t>; 55 friend class DescendTreeCensusClosure<Chunk_t, FreeList_t>; 56 friend class DescendTreeSearchClosure<Chunk_t, FreeList_t>; 57 58 TreeList<Chunk_t, FreeList_t>* _parent; 59 TreeList<Chunk_t, FreeList_t>* _left; 60 TreeList<Chunk_t, FreeList_t>* _right; 61 62 protected: 63 64 TreeList<Chunk_t, FreeList_t>* parent() const { return _parent; } 65 TreeList<Chunk_t, FreeList_t>* left() const { return _left; } 66 TreeList<Chunk_t, FreeList_t>* right() const { return _right; } 67 68 // Wrapper on call to base class, to get the template to compile. 69 Chunk_t* head() const { return FreeList_t::head(); } 70 Chunk_t* tail() const { return FreeList_t::tail(); } 71 void set_head(Chunk_t* head) { FreeList_t::set_head(head); } 72 void set_tail(Chunk_t* tail) { FreeList_t::set_tail(tail); } 73 74 size_t size() const { return FreeList_t::size(); } 75 76 // Accessors for links in tree. 77 78 void set_left(TreeList<Chunk_t, FreeList_t>* tl) { 79 _left = tl; 80 if (tl != NULL) 81 tl->set_parent(this); 82 } 83 void set_right(TreeList<Chunk_t, FreeList_t>* tl) { 84 _right = tl; 85 if (tl != NULL) 86 tl->set_parent(this); 87 } 88 void set_parent(TreeList<Chunk_t, FreeList_t>* tl) { _parent = tl; } 89 90 void clear_left() { _left = NULL; } 91 void clear_right() { _right = NULL; } 92 void clear_parent() { _parent = NULL; } 93 void initialize() { clear_left(); clear_right(), clear_parent(); FreeList_t::initialize(); } 94 95 // For constructing a TreeList from a Tree chunk or 96 // address and size. 97 TreeList(); 98 static TreeList<Chunk_t, FreeList_t>* 99 as_TreeList(TreeChunk<Chunk_t, FreeList_t>* tc); 100 static TreeList<Chunk_t, FreeList_t>* as_TreeList(HeapWord* addr, size_t size); 101 102 // Returns the head of the free list as a pointer to a TreeChunk. 103 TreeChunk<Chunk_t, FreeList_t>* head_as_TreeChunk(); 104 105 // Returns the first available chunk in the free list as a pointer 106 // to a TreeChunk. 107 TreeChunk<Chunk_t, FreeList_t>* first_available(); 108 109 // Returns the block with the largest heap address amongst 110 // those in the list for this size; potentially slow and expensive, 111 // use with caution! 112 TreeChunk<Chunk_t, FreeList_t>* largest_address(); 113 122 // node to point to the new node. 123 TreeList<Chunk_t, FreeList_t>* remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc); 124 // See FreeList. 125 void return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* tc); 126 void return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* tc); 127 }; 128 129 // A TreeChunk is a subclass of a Chunk that additionally 130 // maintains a pointer to the free list on which it is currently 131 // linked. 132 // A TreeChunk is also used as a node in the binary tree. This 133 // allows the binary tree to be maintained without any additional 134 // storage (the free chunks are used). In a binary tree the first 135 // chunk in the free list is also the tree node. Note that the 136 // TreeChunk has an embedded TreeList for this purpose. Because 137 // the first chunk in the list is distinguished in this fashion 138 // (also is the node in the tree), it is the last chunk to be found 139 // on the free list for a node in the tree and is only removed if 140 // it is the last chunk on the free list. 141 142 template <class Chunk_t, class FreeList_t> 143 class TreeChunk : public Chunk_t { 144 friend class TreeList<Chunk_t, FreeList_t>; 145 TreeList<Chunk_t, FreeList_t>* _list; 146 TreeList<Chunk_t, FreeList_t> _embedded_list; // if non-null, this chunk is on _list 147 148 static size_t _min_tree_chunk_size; 149 150 protected: 151 TreeList<Chunk_t, FreeList_t>* embedded_list() const { return (TreeList<Chunk_t, FreeList_t>*) &_embedded_list; } 152 void set_embedded_list(TreeList<Chunk_t, FreeList_t>* v) { _embedded_list = *v; } 153 public: 154 TreeList<Chunk_t, FreeList_t>* list() { return _list; } 155 void set_list(TreeList<Chunk_t, FreeList_t>* v) { _list = v; } 156 static TreeChunk<Chunk_t, FreeList_t>* as_TreeChunk(Chunk_t* fc); 157 // Initialize fields in a TreeChunk that should be 158 // initialized when the TreeChunk is being added to 159 // a free list in the tree. 160 void initialize() { embedded_list()->initialize(); } 161 162 Chunk_t* next() const { return Chunk_t::next(); } 163 Chunk_t* prev() const { return Chunk_t::prev(); } 164 size_t size() const volatile { return Chunk_t::size(); } 165 166 static size_t min_size() { 167 return _min_tree_chunk_size; 168 } 169 170 // debugging 171 void verify_tree_chunk_list() const; 172 void assert_is_mangled() const; 173 }; 174 175 176 template <class Chunk_t, class FreeList_t> 177 class BinaryTreeDictionary: public FreeBlockDictionary<Chunk_t> { 178 friend class VMStructs; 179 size_t _total_size; 180 size_t _total_free_blocks; 181 TreeList<Chunk_t, FreeList_t>* _root; 182 183 // private accessors 184 void set_total_size(size_t v) { _total_size = v; } 185 virtual void inc_total_size(size_t v); 186 virtual void dec_total_size(size_t v); 187 void set_total_free_blocks(size_t v) { _total_free_blocks = v; } 188 TreeList<Chunk_t, FreeList_t>* root() const { return _root; } 189 void set_root(TreeList<Chunk_t, FreeList_t>* v) { _root = v; } 190 191 // This field is added and can be set to point to the 192 // the Mutex used to synchronize access to the 193 // dictionary so that assertion checking can be done. 194 // For example it is set to point to _parDictionaryAllocLock. 195 NOT_PRODUCT(Mutex* _lock;) 196 |