1 /* 2 * Copyright (c) 2009, 2020, 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 */ 24 25 #ifndef SHARE_UTILITIES_STACK_HPP 26 #define SHARE_UTILITIES_STACK_HPP 27 28 #include "memory/allocation.hpp" 29 30 // Class Stack (below) grows and shrinks by linking together "segments" which 31 // are allocated on demand. Segments are arrays of the element type (E) plus an 32 // extra pointer-sized field to store the segment link. Recently emptied 33 // segments are kept in a cache and reused. 34 // 35 // Notes/caveats: 36 // 37 // The size of an element must either evenly divide the size of a pointer or be 38 // a multiple of the size of a pointer. 39 // 40 // Destructors are not called for elements popped off the stack, so element 41 // types which rely on destructors for things like reference counting will not 42 // work properly. 43 // 44 // Class Stack allocates segments from the C heap. However, two protected 45 // virtual methods are used to alloc/free memory which subclasses can override: 46 // 47 // virtual void* alloc(size_t bytes); 48 // virtual void free(void* addr, size_t bytes); 49 // 50 // The alloc() method must return storage aligned for any use. The 51 // implementation in class Stack assumes that alloc() will terminate the process 52 // if the allocation fails. 53 54 template <class E, MEMFLAGS F> class StackIterator; 55 56 // StackBase holds common data/methods that don't depend on the element type, 57 // factored out to reduce template code duplication. 58 template <MEMFLAGS F> class StackBase 59 { 60 public: segment_size() const61 size_t segment_size() const { return _seg_size; } // Elements per segment. max_size() const62 size_t max_size() const { return _max_size; } // Max elements allowed. max_cache_size() const63 size_t max_cache_size() const { return _max_cache_size; } // Max segments 64 // allowed in cache. 65 cache_size() const66 size_t cache_size() const { return _cache_size; } // Segments in the cache. 67 68 protected: 69 // The ctor arguments correspond to the like-named functions above. 70 // segment_size: number of items per segment 71 // max_cache_size: maxmium number of *segments* to cache 72 // max_size: maximum number of items allowed, rounded to a multiple of 73 // the segment size (0 == unlimited) 74 inline StackBase(size_t segment_size, size_t max_cache_size, size_t max_size); 75 76 // Round max_size to a multiple of the segment size. Treat 0 as unlimited. 77 static inline size_t adjust_max_size(size_t max_size, size_t seg_size); 78 79 protected: 80 const size_t _seg_size; // Number of items per segment. 81 const size_t _max_size; // Maximum number of items allowed in the stack. 82 const size_t _max_cache_size; // Maximum number of segments to cache. 83 size_t _cur_seg_size; // Number of items in the current segment. 84 size_t _full_seg_size; // Number of items in already-filled segments. 85 size_t _cache_size; // Number of segments in the cache. 86 }; 87 88 template <class E, MEMFLAGS F> 89 class Stack: public StackBase<F> 90 { 91 public: 92 friend class StackIterator<E, F>; 93 94 // Number of elements that fit in 4K bytes minus the size of two pointers 95 // (link field and malloc header). 96 static const size_t _default_segment_size = (4096 - 2 * sizeof(E*)) / sizeof(E); default_segment_size()97 static size_t default_segment_size() { return _default_segment_size; } 98 99 // segment_size: number of items per segment 100 // max_cache_size: maxmium number of *segments* to cache 101 // max_size: maximum number of items allowed, rounded to a multiple of 102 // the segment size (0 == unlimited) 103 inline Stack(size_t segment_size = _default_segment_size, 104 size_t max_cache_size = 4, size_t max_size = 0); ~Stack()105 inline ~Stack() { clear(true); } 106 is_empty() const107 inline bool is_empty() const { return this->_cur_seg == NULL; } is_full() const108 inline bool is_full() const { return this->_full_seg_size >= this->max_size(); } 109 110 // Performance sensitive code should use is_empty() instead of size() == 0 and 111 // is_full() instead of size() == max_size(). Using a conditional here allows 112 // just one var to be updated when pushing/popping elements instead of two; 113 // _full_seg_size is updated only when pushing/popping segments. size() const114 inline size_t size() const { 115 return is_empty() ? 0 : this->_full_seg_size + this->_cur_seg_size; 116 } 117 118 inline void push(E elem); 119 inline E pop(); 120 121 // Clear everything from the stack, releasing the associated memory. If 122 // clear_cache is true, also release any cached segments. 123 void clear(bool clear_cache = false); 124 125 protected: 126 // Each segment includes space for _seg_size elements followed by a link 127 // (pointer) to the previous segment; the space is allocated as a single block 128 // of size segment_bytes(). _seg_size is rounded up if necessary so the link 129 // is properly aligned. The C struct for the layout would be: 130 // 131 // struct segment { 132 // E elements[_seg_size]; 133 // E* link; 134 // }; 135 136 // Round up seg_size to keep the link field aligned. 137 static inline size_t adjust_segment_size(size_t seg_size); 138 139 // Methods for allocation size and getting/setting the link. 140 inline size_t link_offset() const; // Byte offset of link field. 141 inline size_t segment_bytes() const; // Segment size in bytes. 142 inline E** link_addr(E* seg) const; // Address of the link field. 143 inline E* get_link(E* seg) const; // Extract the link from seg. 144 inline E* set_link(E* new_seg, E* old_seg); // new_seg.link = old_seg. 145 146 virtual E* alloc(size_t bytes); 147 virtual void free(E* addr, size_t bytes); 148 149 void push_segment(); 150 void pop_segment(); 151 152 void free_segments(E* seg); // Free all segments in the list. 153 inline void reset(bool reset_cache); // Reset all data fields. 154 155 DEBUG_ONLY(void verify(bool at_empty_transition) const;) 156 DEBUG_ONLY(void zap_segment(E* seg, bool zap_link_field) const;) 157 158 private: 159 E* _cur_seg; // Current segment. 160 E* _cache; // Segment cache to avoid ping-ponging. 161 }; 162 163 template <class E, MEMFLAGS F> class ResourceStack: public Stack<E, F>, public ResourceObj 164 { 165 public: 166 // If this class becomes widely used, it may make sense to save the Thread 167 // and use it when allocating segments. 168 // ResourceStack(size_t segment_size = Stack<E, F>::default_segment_size()): ResourceStack(size_t segment_size)169 ResourceStack(size_t segment_size): Stack<E, F>(segment_size, max_uintx) 170 { } 171 172 // Set the segment pointers to NULL so the parent dtor does not free them; 173 // that must be done by the ResourceMark code. ~ResourceStack()174 ~ResourceStack() { Stack<E, F>::reset(true); } 175 176 protected: 177 virtual E* alloc(size_t bytes); 178 virtual void free(E* addr, size_t bytes); 179 180 private: 181 void clear(bool clear_cache = false); 182 }; 183 184 template <class E, MEMFLAGS F> 185 class StackIterator: public StackObj 186 { 187 public: StackIterator(Stack<E,F> & stack)188 StackIterator(Stack<E, F>& stack): _stack(stack) { sync(); } 189 stack() const190 Stack<E, F>& stack() const { return _stack; } 191 is_empty() const192 bool is_empty() const { return _cur_seg == NULL; } 193 next()194 E next() { return *next_addr(); } 195 E* next_addr(); 196 197 void sync(); // Sync the iterator's state to the stack's current state. 198 199 private: 200 Stack<E, F>& _stack; 201 size_t _cur_seg_size; 202 E* _cur_seg; 203 size_t _full_seg_size; 204 }; 205 206 #endif // SHARE_UTILITIES_STACK_HPP 207