Mercurial > hg > graal-compiler

comparison src/share/vm/utilities/stack.hpp @ 1836:894b1d7c7e01

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