stack.inline.hpp revision 8161:4b1c654a2c53
1144518Sdavidxu/* 2144518Sdavidxu * Copyright (c) 2009, 2014, Oracle and/or its affiliates. All rights reserved. 3144518Sdavidxu * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4144518Sdavidxu * 5144518Sdavidxu * This code is free software; you can redistribute it and/or modify it 6144518Sdavidxu * under the terms of the GNU General Public License version 2 only, as 7144518Sdavidxu * published by the Free Software Foundation. 8144518Sdavidxu * 9144518Sdavidxu * This code is distributed in the hope that it will be useful, but WITHOUT 10144518Sdavidxu * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11144518Sdavidxu * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12144518Sdavidxu * version 2 for more details (a copy is included in the LICENSE file that 13144518Sdavidxu * accompanied this code). 14144518Sdavidxu * 15144518Sdavidxu * You should have received a copy of the GNU General Public License version 16144518Sdavidxu * 2 along with this work; if not, write to the Free Software Foundation, 17144518Sdavidxu * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18144518Sdavidxu * 19144518Sdavidxu * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20144518Sdavidxu * or visit www.oracle.com if you need additional information or have any 21144518Sdavidxu * questions. 22144518Sdavidxu * 23144518Sdavidxu */ 24144518Sdavidxu 25144518Sdavidxu#ifndef SHARE_VM_UTILITIES_STACK_INLINE_HPP 26144518Sdavidxu#define SHARE_VM_UTILITIES_STACK_INLINE_HPP 27144518Sdavidxu 28144518Sdavidxu#include "utilities/stack.hpp" 29144518Sdavidxu 30144518Sdavidxutemplate <MEMFLAGS F> StackBase<F>::StackBase(size_t segment_size, size_t max_cache_size, 31144518Sdavidxu size_t max_size): 32144518Sdavidxu _seg_size(segment_size), 33177853Sdavidxu _max_cache_size(max_cache_size), 34177853Sdavidxu _max_size(adjust_max_size(max_size, segment_size)) 35177853Sdavidxu{ 36177853Sdavidxu assert(_max_size % _seg_size == 0, "not a multiple"); 37177853Sdavidxu} 38177853Sdavidxu 39177853Sdavidxutemplate <MEMFLAGS F> size_t StackBase<F>::adjust_max_size(size_t max_size, size_t seg_size) 40177853Sdavidxu{ 41177853Sdavidxu assert(seg_size > 0, "cannot be 0"); 42163334Sdavidxu assert(max_size >= seg_size || max_size == 0, "max_size too small"); 43163334Sdavidxu const size_t limit = max_uintx - (seg_size - 1); 44163334Sdavidxu if (max_size == 0 || max_size > limit) { 45163334Sdavidxu max_size = limit; 46163334Sdavidxu } 47163334Sdavidxu return (max_size + seg_size - 1) / seg_size * seg_size; 48163334Sdavidxu} 49163334Sdavidxu 50212077Sdavidxutemplate <class E, MEMFLAGS F> 51212077SdavidxuStack<E, F>::Stack(size_t segment_size, size_t max_cache_size, size_t max_size): 52212077Sdavidxu StackBase<F>(adjust_segment_size(segment_size), max_cache_size, max_size) 53212077Sdavidxu{ 54212077Sdavidxu reset(true); 55212077Sdavidxu} 56212077Sdavidxu 57144518Sdavidxutemplate <class E, MEMFLAGS F> 58179970Sdavidxuvoid Stack<E, F>::push(E item) 59161680Sdavidxu{ 60179970Sdavidxu assert(!is_full(), "pushing onto a full stack"); 61179970Sdavidxu if (this->_cur_seg_size == this->_seg_size) { 62179970Sdavidxu push_segment(); 63179970Sdavidxu } 64179970Sdavidxu this->_cur_seg[this->_cur_seg_size] = item; 65179970Sdavidxu ++this->_cur_seg_size; 66179970Sdavidxu} 67179970Sdavidxu 68179970Sdavidxutemplate <class E, MEMFLAGS F> 69179970SdavidxuE Stack<E, F>::pop() 70179970Sdavidxu{ 71179970Sdavidxu assert(!is_empty(), "popping from an empty stack"); 72179970Sdavidxu if (this->_cur_seg_size == 1) { 73179970Sdavidxu E tmp = _cur_seg[--this->_cur_seg_size]; 74179970Sdavidxu pop_segment(); 75161680Sdavidxu return tmp; 76161680Sdavidxu } 77216641Sdavidxu return this->_cur_seg[--this->_cur_seg_size]; 78216641Sdavidxu} 79161680Sdavidxu 80216641Sdavidxutemplate <class E, MEMFLAGS F> 81216641Sdavidxuvoid Stack<E, F>::clear(bool clear_cache) 82216641Sdavidxu{ 83216641Sdavidxu free_segments(_cur_seg); 84216641Sdavidxu if (clear_cache) free_segments(_cache); 85216641Sdavidxu reset(clear_cache); 86216641Sdavidxu} 87216641Sdavidxu 88216641Sdavidxutemplate <class E, MEMFLAGS F> 89216641Sdavidxusize_t Stack<E, F>::adjust_segment_size(size_t seg_size) 90216641Sdavidxu{ 91216641Sdavidxu const size_t elem_sz = sizeof(E); 92216641Sdavidxu const size_t ptr_sz = sizeof(E*); 93216641Sdavidxu assert(elem_sz % ptr_sz == 0 || ptr_sz % elem_sz == 0, "bad element size"); 94216641Sdavidxu if (elem_sz < ptr_sz) { 95216641Sdavidxu return align_size_up(seg_size * elem_sz, ptr_sz) / elem_sz; 96216641Sdavidxu } 97216641Sdavidxu return seg_size; 98216641Sdavidxu} 99216641Sdavidxu 100216641Sdavidxutemplate <class E, MEMFLAGS F> 101216641Sdavidxusize_t Stack<E, F>::link_offset() const 102216641Sdavidxu{ 103216641Sdavidxu return align_size_up(this->_seg_size * sizeof(E), sizeof(E*)); 104216641Sdavidxu} 105216641Sdavidxu 106216641Sdavidxutemplate <class E, MEMFLAGS F> 107216641Sdavidxusize_t Stack<E, F>::segment_bytes() const 108216641Sdavidxu{ 109216641Sdavidxu return link_offset() + sizeof(E*); 110216641Sdavidxu} 111179970Sdavidxu 112179970Sdavidxutemplate <class E, MEMFLAGS F> 113161680SdavidxuE** Stack<E, F>::link_addr(E* seg) const 114179970Sdavidxu{ 115179970Sdavidxu return (E**) ((char*)seg + link_offset()); 116179970Sdavidxu} 117179970Sdavidxu 118179970Sdavidxutemplate <class E, MEMFLAGS F> 119179970SdavidxuE* Stack<E, F>::get_link(E* seg) const 120179970Sdavidxu{ 121179970Sdavidxu return *link_addr(seg); 122161680Sdavidxu} 123179970Sdavidxu 124179970Sdavidxutemplate <class E, MEMFLAGS F> 125179970SdavidxuE* Stack<E, F>::set_link(E* new_seg, E* old_seg) 126179970Sdavidxu{ 127179970Sdavidxu *link_addr(new_seg) = old_seg; 128179970Sdavidxu return new_seg; 129179970Sdavidxu} 130179970Sdavidxu 131179970Sdavidxutemplate <class E, MEMFLAGS F> 132179970SdavidxuE* Stack<E, F>::alloc(size_t bytes) 133179970Sdavidxu{ 134179970Sdavidxu return (E*) NEW_C_HEAP_ARRAY(char, bytes, F); 135179970Sdavidxu} 136179970Sdavidxu 137179970Sdavidxutemplate <class E, MEMFLAGS F> 138179970Sdavidxuvoid Stack<E, F>::free(E* addr, size_t bytes) 139179970Sdavidxu{ 140179970Sdavidxu FREE_C_HEAP_ARRAY(char, (char*) addr); 141179970Sdavidxu} 142179970Sdavidxu 143179970Sdavidxutemplate <class E, MEMFLAGS F> 144179970Sdavidxuvoid Stack<E, F>::push_segment() 145179970Sdavidxu{ 146179970Sdavidxu assert(this->_cur_seg_size == this->_seg_size, "current segment is not full"); 147179970Sdavidxu E* next; 148179970Sdavidxu if (this->_cache_size > 0) { 149179970Sdavidxu // Use a cached segment. 150161680Sdavidxu next = _cache; 151161680Sdavidxu _cache = get_link(_cache); 152161680Sdavidxu --this->_cache_size; 153179970Sdavidxu } else { 154161680Sdavidxu next = alloc(segment_bytes()); 155200498Smarcel DEBUG_ONLY(zap_segment(next, true);) 156200498Smarcel } 157179970Sdavidxu const bool at_empty_transition = is_empty(); 158179970Sdavidxu this->_cur_seg = set_link(next, _cur_seg); 159179970Sdavidxu this->_cur_seg_size = 0; 160179970Sdavidxu this->_full_seg_size += at_empty_transition ? 0 : this->_seg_size; 161200498Smarcel DEBUG_ONLY(verify(at_empty_transition);) 162177853Sdavidxu} 163161680Sdavidxu 164161680Sdavidxutemplate <class E, MEMFLAGS F> 165161680Sdavidxuvoid Stack<E, F>::pop_segment() 166163334Sdavidxu{ 167161680Sdavidxu assert(this->_cur_seg_size == 0, "current segment is not empty"); 168177853Sdavidxu E* const prev = get_link(_cur_seg); 169161680Sdavidxu if (this->_cache_size < this->_max_cache_size) { 170161680Sdavidxu // Add the current segment to the cache. 171161680Sdavidxu DEBUG_ONLY(zap_segment(_cur_seg, false);) 172161680Sdavidxu _cache = set_link(_cur_seg, _cache); 173161680Sdavidxu ++this->_cache_size; 174161680Sdavidxu } else { 175177853Sdavidxu DEBUG_ONLY(zap_segment(_cur_seg, true);) 176161680Sdavidxu free(_cur_seg, segment_bytes()); 177161680Sdavidxu } 178161680Sdavidxu const bool at_empty_transition = prev == NULL; 179173801Sdavidxu this->_cur_seg = prev; 180144518Sdavidxu this->_cur_seg_size = this->_seg_size; 181144518Sdavidxu this->_full_seg_size -= at_empty_transition ? 0 : this->_seg_size; 182144518Sdavidxu DEBUG_ONLY(verify(at_empty_transition);) 183144518Sdavidxu} 184177853Sdavidxu 185177853Sdavidxutemplate <class E, MEMFLAGS F> 186144518Sdavidxuvoid Stack<E, F>::free_segments(E* seg) 187144518Sdavidxu{ 188144518Sdavidxu const size_t bytes = segment_bytes(); 189178647Sdavidxu while (seg != NULL) { 190144518Sdavidxu E* const prev = get_link(seg); 191173801Sdavidxu free(seg, bytes); 192173801Sdavidxu seg = prev; 193173801Sdavidxu } 194178647Sdavidxu} 195178647Sdavidxu 196178647Sdavidxutemplate <class E, MEMFLAGS F> 197173801Sdavidxuvoid Stack<E, F>::reset(bool reset_cache) 198173801Sdavidxu{ 199173801Sdavidxu this->_cur_seg_size = this->_seg_size; // So push() will alloc a new segment. 200216641Sdavidxu this->_full_seg_size = 0; 201216641Sdavidxu _cur_seg = NULL; 202216641Sdavidxu if (reset_cache) { 203216641Sdavidxu this->_cache_size = 0; 204231989Sdavidxu _cache = NULL; 205231989Sdavidxu } 206231989Sdavidxu} 207216641Sdavidxu 208216641Sdavidxu#ifdef ASSERT 209216641Sdavidxutemplate <class E, MEMFLAGS F> 210178647Sdavidxuvoid Stack<E, F>::verify(bool at_empty_transition) const 211173801Sdavidxu{ 212178647Sdavidxu assert(size() <= this->max_size(), "stack exceeded bounds"); 213177853Sdavidxu assert(this->cache_size() <= this->max_cache_size(), "cache exceeded bounds"); 214144518Sdavidxu assert(this->_cur_seg_size <= this->segment_size(), "segment index exceeded bounds"); 215164877Sdavidxu 216164902Sdavidxu assert(this->_full_seg_size % this->_seg_size == 0, "not a multiple"); 217164902Sdavidxu assert(at_empty_transition || is_empty() == (size() == 0), "mismatch"); 218164902Sdavidxu assert((_cache == NULL) == (this->cache_size() == 0), "mismatch"); 219164902Sdavidxu 220164902Sdavidxu if (is_empty()) { 221164902Sdavidxu assert(this->_cur_seg_size == this->segment_size(), "sanity"); 222164877Sdavidxu } 223164877Sdavidxu} 224227604Sdavidxu 225164877Sdavidxutemplate <class E, MEMFLAGS F> 226164877Sdavidxuvoid Stack<E, F>::zap_segment(E* seg, bool zap_link_field) const 227164877Sdavidxu{ 228179970Sdavidxu if (!ZapStackSegments) return; 229179970Sdavidxu const size_t zap_bytes = segment_bytes() - (zap_link_field ? 0 : sizeof(E*)); 230164877Sdavidxu uint32_t* cur = (uint32_t*)seg; 231164877Sdavidxu const uint32_t* end = cur + zap_bytes / sizeof(uint32_t); 232227604Sdavidxu while (cur < end) { 233177853Sdavidxu *cur++ = 0xfadfaded; 234164877Sdavidxu } 235164877Sdavidxu} 236164877Sdavidxu#endif 237164877Sdavidxu 238164877Sdavidxutemplate <class E, MEMFLAGS F> 239165110SdavidxuE* ResourceStack<E, F>::alloc(size_t bytes) 240165110Sdavidxu{ 241177853Sdavidxu return (E*) resource_allocate_bytes(bytes); 242164877Sdavidxu} 243164877Sdavidxu 244164877Sdavidxutemplate <class E, MEMFLAGS F> 245164877Sdavidxuvoid ResourceStack<E, F>::free(E* addr, size_t bytes) 246164877Sdavidxu{ 247165110Sdavidxu resource_free_bytes((char*) addr, bytes); 248165110Sdavidxu} 249177853Sdavidxu 250164877Sdavidxutemplate <class E, MEMFLAGS F> 251177850Sdavidxuvoid StackIterator<E, F>::sync() 252177850Sdavidxu{ 253177850Sdavidxu _full_seg_size = _stack._full_seg_size; 254177850Sdavidxu _cur_seg_size = _stack._cur_seg_size; 255177853Sdavidxu _cur_seg = _stack._cur_seg; 256177850Sdavidxu} 257177850Sdavidxu 258177850Sdavidxutemplate <class E, MEMFLAGS F> 259177850SdavidxuE* StackIterator<E, F>::next_addr() 260177850Sdavidxu{ 261177853Sdavidxu assert(!is_empty(), "no items left"); 262177850Sdavidxu if (_cur_seg_size == 1) { 263177850Sdavidxu E* addr = _cur_seg; 264177850Sdavidxu _cur_seg = _stack.get_link(_cur_seg); 265177850Sdavidxu _cur_seg_size = _stack.segment_size(); 266177850Sdavidxu _full_seg_size -= _stack.segment_size(); 267177853Sdavidxu return addr; 268177850Sdavidxu } 269212076Sdavidxu return _cur_seg + --_cur_seg_size; 270212076Sdavidxu} 271212076Sdavidxu 272212076Sdavidxu#endif // SHARE_VM_UTILITIES_STACK_INLINE_HPP 273212076Sdavidxu