Mercurial > hg > graal-compiler

comparison src/share/vm/utilities/stack.inline.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 StackBase::StackBase(size_t segment_size, size_t max_cache_size,
26 size_t max_size):
27 _seg_size(segment_size),
28 _max_cache_size(max_cache_size),
29 _max_size(adjust_max_size(max_size, segment_size))
30 {
31 assert(_max_size % _seg_size == 0, "not a multiple");
32 }
33
34 size_t StackBase::adjust_max_size(size_t max_size, size_t seg_size)
35 {
36 assert(seg_size > 0, "cannot be 0");
37 assert(max_size >= seg_size || max_size == 0, "max_size too small");
38 const size_t limit = max_uintx - (seg_size - 1);
39 if (max_size == 0 || max_size > limit) {
40 max_size = limit;
41 }
42 return (max_size + seg_size - 1) / seg_size * seg_size;
43 }
44
45 template <class E>
46 Stack<E>::Stack(size_t segment_size, size_t max_cache_size, size_t max_size):
47 StackBase(adjust_segment_size(segment_size), max_cache_size, max_size)
48 {
49 reset(true);
50 }
51
52 template <class E>
53 void Stack<E>::push(E item)
54 {
55 assert(!is_full(), "pushing onto a full stack");
56 if (_cur_seg_size == _seg_size) {
57 push_segment();
58 }
59 _cur_seg[_cur_seg_size] = item;
60 ++_cur_seg_size;
61 }
62
63 template <class E>
64 E Stack<E>::pop()
65 {
66 assert(!is_empty(), "popping from an empty stack");
67 if (_cur_seg_size == 1) {
68 E tmp = _cur_seg[--_cur_seg_size];
69 pop_segment();
70 return tmp;
71 }
72 return _cur_seg[--_cur_seg_size];
73 }
74
75 template <class E>
76 void Stack<E>::clear(bool clear_cache)
77 {
78 free_segments(_cur_seg);
79 if (clear_cache) free_segments(_cache);
80 reset(clear_cache);
81 }
82
83 template <class E>
84 size_t Stack<E>::default_segment_size()
85 {
86 // Number of elements that fit in 4K bytes minus the size of two pointers
87 // (link field and malloc header).
88 return (4096 - 2 * sizeof(E*)) / sizeof(E);
89 }
90
91 template <class E>
92 size_t Stack<E>::adjust_segment_size(size_t seg_size)
93 {
94 const size_t elem_sz = sizeof(E);
95 const size_t ptr_sz = sizeof(E*);
96 assert(elem_sz % ptr_sz == 0 || ptr_sz % elem_sz == 0, "bad element size");
97 if (elem_sz < ptr_sz) {
98 return align_size_up(seg_size * elem_sz, ptr_sz) / elem_sz;
99 }
100 return seg_size;
101 }
102
103 template <class E>
104 size_t Stack<E>::link_offset() const
105 {
106 return align_size_up(_seg_size * sizeof(E), sizeof(E*));
107 }
108
109 template <class E>
110 size_t Stack<E>::segment_bytes() const
111 {
112 return link_offset() + sizeof(E*);
113 }
114
115 template <class E>
116 E** Stack<E>::link_addr(E* seg) const
117 {
118 return (E**) ((char*)seg + link_offset());
119 }
120
121 template <class E>
122 E* Stack<E>::get_link(E* seg) const
123 {
124 return *link_addr(seg);
125 }
126
127 template <class E>
128 E* Stack<E>::set_link(E* new_seg, E* old_seg)
129 {
130 *link_addr(new_seg) = old_seg;
131 return new_seg;
132 }
133
134 template <class E>
135 E* Stack<E>::alloc(size_t bytes)
136 {
137 return (E*) NEW_C_HEAP_ARRAY(char, bytes);
138 }
139
140 template <class E>
141 void Stack<E>::free(E* addr, size_t bytes)
142 {
143 FREE_C_HEAP_ARRAY(char, (char*) addr);
144 }
145
146 template <class E>
147 void Stack<E>::push_segment()
148 {
149 assert(_cur_seg_size == _seg_size, "current segment is not full");
150 E* next;
151 if (_cache_size > 0) {
152 // Use a cached segment.
153 next = _cache;
154 _cache = get_link(_cache);
155 --_cache_size;
156 } else {
157 next = alloc(segment_bytes());
158 DEBUG_ONLY(zap_segment(next, true);)
159 }
160 const bool at_empty_transition = is_empty();
161 _cur_seg = set_link(next, _cur_seg);
162 _cur_seg_size = 0;
163 _full_seg_size += at_empty_transition ? 0 : _seg_size;
164 DEBUG_ONLY(verify(at_empty_transition);)
165 }
166
167 template <class E>
168 void Stack<E>::pop_segment()
169 {
170 assert(_cur_seg_size == 0, "current segment is not empty");
171 E* const prev = get_link(_cur_seg);
172 if (_cache_size < _max_cache_size) {
173 // Add the current segment to the cache.
174 DEBUG_ONLY(zap_segment(_cur_seg, false);)
175 _cache = set_link(_cur_seg, _cache);
176 ++_cache_size;
177 } else {
178 DEBUG_ONLY(zap_segment(_cur_seg, true);)
179 free(_cur_seg, segment_bytes());
180 }
181 const bool at_empty_transition = prev == NULL;
182 _cur_seg = prev;
183 _cur_seg_size = _seg_size;
184 _full_seg_size -= at_empty_transition ? 0 : _seg_size;
185 DEBUG_ONLY(verify(at_empty_transition);)
186 }
187
188 template <class E>
189 void Stack<E>::free_segments(E* seg)
190 {
191 const size_t bytes = segment_bytes();
192 while (seg != NULL) {
193 E* const prev = get_link(seg);
194 free(seg, bytes);
195 seg = prev;
196 }
197 }
198
199 template <class E>
200 void Stack<E>::reset(bool reset_cache)
201 {
202 _cur_seg_size = _seg_size; // So push() will alloc a new segment.
203 _full_seg_size = 0;
204 _cur_seg = NULL;
205 if (reset_cache) {
206 _cache_size = 0;
207 _cache = NULL;
208 }
209 }
210
211 #ifdef ASSERT
212 template <class E>
213 void Stack<E>::verify(bool at_empty_transition) const
214 {
215 assert(size() <= max_size(), "stack exceeded bounds");
216 assert(cache_size() <= max_cache_size(), "cache exceeded bounds");
217 assert(_cur_seg_size <= segment_size(), "segment index exceeded bounds");
218
219 assert(_full_seg_size % _seg_size == 0, "not a multiple");
220 assert(at_empty_transition || is_empty() == (size() == 0), "mismatch");
221 assert((_cache == NULL) == (cache_size() == 0), "mismatch");
222
223 if (is_empty()) {
224 assert(_cur_seg_size == segment_size(), "sanity");
225 }
226 }
227
228 template <class E>
229 void Stack<E>::zap_segment(E* seg, bool zap_link_field) const
230 {
231 if (!ZapStackSegments) return;
232 const size_t zap_bytes = segment_bytes() - (zap_link_field ? 0 : sizeof(E*));
233 uint32_t* cur = (uint32_t*)seg;
234 const uint32_t* end = cur + zap_bytes / sizeof(uint32_t);
235 while (cur < end) {
236 *cur++ = 0xfadfaded;
237 }
238 }
239 #endif
240
241 template <class E>
242 E* ResourceStack<E>::alloc(size_t bytes)
243 {
244 return (E*) resource_allocate_bytes(bytes);
245 }
246
247 template <class E>
248 void ResourceStack<E>::free(E* addr, size_t bytes)
249 {
250 resource_free_bytes((char*) addr, bytes);
251 }
252
253 template <class E>
254 void StackIterator<E>::sync()
255 {
256 _full_seg_size = _stack._full_seg_size;
257 _cur_seg_size = _stack._cur_seg_size;
258 _cur_seg = _stack._cur_seg;
259 }
260
261 template <class E>
262 E* StackIterator<E>::next_addr()
263 {
264 assert(!is_empty(), "no items left");
265 if (_cur_seg_size == 1) {
266 E* addr = _cur_seg;
267 _cur_seg = _stack.get_link(_cur_seg);
268 _cur_seg_size = _stack.segment_size();
269 _full_seg_size -= _stack.segment_size();
270 return addr;
271 }
272 return _cur_seg + --_cur_seg_size;
273 }