jcoomes@2191: /*
jcoomes@2191:  * Copyright 2009 Sun Microsystems, Inc.  All Rights Reserved.
jcoomes@2191:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
jcoomes@2191:  *
jcoomes@2191:  * This code is free software; you can redistribute it and/or modify it
jcoomes@2191:  * under the terms of the GNU General Public License version 2 only, as
jcoomes@2191:  * published by the Free Software Foundation.
jcoomes@2191:  *
jcoomes@2191:  * This code is distributed in the hope that it will be useful, but WITHOUT
jcoomes@2191:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
jcoomes@2191:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
jcoomes@2191:  * version 2 for more details (a copy is included in the LICENSE file that
jcoomes@2191:  * accompanied this code).
jcoomes@2191:  *
jcoomes@2191:  * You should have received a copy of the GNU General Public License version
jcoomes@2191:  * 2 along with this work; if not, write to the Free Software Foundation,
jcoomes@2191:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
jcoomes@2191:  *
jcoomes@2191:  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
jcoomes@2191:  * CA 95054 USA or visit www.sun.com if you need additional information or
jcoomes@2191:  * have any questions.
jcoomes@2191:  *
jcoomes@2191:  */
jcoomes@2191: 
jcoomes@2191: StackBase::StackBase(size_t segment_size, size_t max_cache_size,
jcoomes@2191:                      size_t max_size):
jcoomes@2191:   _seg_size(segment_size),
jcoomes@2191:   _max_cache_size(max_cache_size),
jcoomes@2191:   _max_size(adjust_max_size(max_size, segment_size))
jcoomes@2191: {
jcoomes@2191:   assert(_max_size % _seg_size == 0, "not a multiple");
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: size_t StackBase::adjust_max_size(size_t max_size, size_t seg_size)
jcoomes@2191: {
jcoomes@2191:   assert(seg_size > 0, "cannot be 0");
jcoomes@2191:   assert(max_size >= seg_size || max_size == 0, "max_size too small");
jcoomes@2191:   const size_t limit = max_uintx - (seg_size - 1);
jcoomes@2191:   if (max_size == 0 || max_size > limit) {
jcoomes@2191:     max_size = limit;
jcoomes@2191:   }
jcoomes@2191:   return (max_size + seg_size - 1) / seg_size * seg_size;
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: Stack<E>::Stack(size_t segment_size, size_t max_cache_size, size_t max_size):
jcoomes@2191:   StackBase(adjust_segment_size(segment_size), max_cache_size, max_size)
jcoomes@2191: {
jcoomes@2191:   reset(true);
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: void Stack<E>::push(E item)
jcoomes@2191: {
jcoomes@2191:   assert(!is_full(), "pushing onto a full stack");
jcoomes@2191:   if (_cur_seg_size == _seg_size) {
jcoomes@2191:     push_segment();
jcoomes@2191:   }
jcoomes@2191:   _cur_seg[_cur_seg_size] = item;
jcoomes@2191:   ++_cur_seg_size;
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: E Stack<E>::pop()
jcoomes@2191: {
jcoomes@2191:   assert(!is_empty(), "popping from an empty stack");
jcoomes@2191:   if (_cur_seg_size == 1) {
jcoomes@2191:     E tmp = _cur_seg[--_cur_seg_size];
jcoomes@2191:     pop_segment();
jcoomes@2191:     return tmp;
jcoomes@2191:   }
jcoomes@2191:   return _cur_seg[--_cur_seg_size];
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: void Stack<E>::clear(bool clear_cache)
jcoomes@2191: {
jcoomes@2191:   free_segments(_cur_seg);
jcoomes@2191:   if (clear_cache) free_segments(_cache);
jcoomes@2191:   reset(clear_cache);
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: size_t Stack<E>::default_segment_size()
jcoomes@2191: {
jcoomes@2191:   // Number of elements that fit in 4K bytes minus the size of two pointers
jcoomes@2191:   // (link field and malloc header).
jcoomes@2191:   return (4096 - 2 * sizeof(E*)) / sizeof(E);
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: size_t Stack<E>::adjust_segment_size(size_t seg_size)
jcoomes@2191: {
jcoomes@2191:   const size_t elem_sz = sizeof(E);
jcoomes@2191:   const size_t ptr_sz = sizeof(E*);
jcoomes@2191:   assert(elem_sz % ptr_sz == 0 || ptr_sz % elem_sz == 0, "bad element size");
jcoomes@2191:   if (elem_sz < ptr_sz) {
jcoomes@2191:     return align_size_up(seg_size * elem_sz, ptr_sz) / elem_sz;
jcoomes@2191:   }
jcoomes@2191:   return seg_size;
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: size_t Stack<E>::link_offset() const
jcoomes@2191: {
jcoomes@2191:   return align_size_up(_seg_size * sizeof(E), sizeof(E*));
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: size_t Stack<E>::segment_bytes() const
jcoomes@2191: {
jcoomes@2191:   return link_offset() + sizeof(E*);
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: E** Stack<E>::link_addr(E* seg) const
jcoomes@2191: {
jcoomes@2191:   return (E**) ((char*)seg + link_offset());
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: E* Stack<E>::get_link(E* seg) const
jcoomes@2191: {
jcoomes@2191:   return *link_addr(seg);
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: E* Stack<E>::set_link(E* new_seg, E* old_seg)
jcoomes@2191: {
jcoomes@2191:   *link_addr(new_seg) = old_seg;
jcoomes@2191:   return new_seg;
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: E* Stack<E>::alloc(size_t bytes)
jcoomes@2191: {
jcoomes@2191:   return (E*) NEW_C_HEAP_ARRAY(char, bytes);
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: void Stack<E>::free(E* addr, size_t bytes)
jcoomes@2191: {
jcoomes@2191:   FREE_C_HEAP_ARRAY(char, (char*) addr);
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: void Stack<E>::push_segment()
jcoomes@2191: {
jcoomes@2191:   assert(_cur_seg_size == _seg_size, "current segment is not full");
jcoomes@2191:   E* next;
jcoomes@2191:   if (_cache_size > 0) {
jcoomes@2191:     // Use a cached segment.
jcoomes@2191:     next = _cache;
jcoomes@2191:     _cache = get_link(_cache);
jcoomes@2191:     --_cache_size;
jcoomes@2191:   } else {
jcoomes@2191:     next = alloc(segment_bytes());
jcoomes@2191:     DEBUG_ONLY(zap_segment(next, true);)
jcoomes@2191:   }
jcoomes@2191:   const bool at_empty_transition = is_empty();
jcoomes@2191:   _cur_seg = set_link(next, _cur_seg);
jcoomes@2191:   _cur_seg_size = 0;
jcoomes@2191:   _full_seg_size += at_empty_transition ? 0 : _seg_size;
jcoomes@2191:   DEBUG_ONLY(verify(at_empty_transition);)
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: void Stack<E>::pop_segment()
jcoomes@2191: {
jcoomes@2191:   assert(_cur_seg_size == 0, "current segment is not empty");
jcoomes@2191:   E* const prev = get_link(_cur_seg);
jcoomes@2191:   if (_cache_size < _max_cache_size) {
jcoomes@2191:     // Add the current segment to the cache.
jcoomes@2191:     DEBUG_ONLY(zap_segment(_cur_seg, false);)
jcoomes@2191:     _cache = set_link(_cur_seg, _cache);
jcoomes@2191:     ++_cache_size;
jcoomes@2191:   } else {
jcoomes@2191:     DEBUG_ONLY(zap_segment(_cur_seg, true);)
jcoomes@2191:     free(_cur_seg, segment_bytes());
jcoomes@2191:   }
jcoomes@2191:   const bool at_empty_transition = prev == NULL;
jcoomes@2191:   _cur_seg = prev;
jcoomes@2191:   _cur_seg_size = _seg_size;
jcoomes@2191:   _full_seg_size -= at_empty_transition ? 0 : _seg_size;
jcoomes@2191:   DEBUG_ONLY(verify(at_empty_transition);)
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: void Stack<E>::free_segments(E* seg)
jcoomes@2191: {
jcoomes@2191:   const size_t bytes = segment_bytes();
jcoomes@2191:   while (seg != NULL) {
jcoomes@2191:     E* const prev = get_link(seg);
jcoomes@2191:     free(seg, bytes);
jcoomes@2191:     seg = prev;
jcoomes@2191:   }
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: void Stack<E>::reset(bool reset_cache)
jcoomes@2191: {
jcoomes@2191:   _cur_seg_size = _seg_size; // So push() will alloc a new segment.
jcoomes@2191:   _full_seg_size = 0;
jcoomes@2191:   _cur_seg = NULL;
jcoomes@2191:   if (reset_cache) {
jcoomes@2191:     _cache_size = 0;
jcoomes@2191:     _cache = NULL;
jcoomes@2191:   }
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: #ifdef ASSERT
jcoomes@2191: template <class E>
jcoomes@2191: void Stack<E>::verify(bool at_empty_transition) const
jcoomes@2191: {
jcoomes@2191:   assert(size() <= max_size(), "stack exceeded bounds");
jcoomes@2191:   assert(cache_size() <= max_cache_size(), "cache exceeded bounds");
jcoomes@2191:   assert(_cur_seg_size <= segment_size(), "segment index exceeded bounds");
jcoomes@2191: 
jcoomes@2191:   assert(_full_seg_size % _seg_size == 0, "not a multiple");
jcoomes@2191:   assert(at_empty_transition || is_empty() == (size() == 0), "mismatch");
jcoomes@2191:   assert((_cache == NULL) == (cache_size() == 0), "mismatch");
jcoomes@2191: 
jcoomes@2191:   if (is_empty()) {
jcoomes@2191:     assert(_cur_seg_size == segment_size(), "sanity");
jcoomes@2191:   }
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: void Stack<E>::zap_segment(E* seg, bool zap_link_field) const
jcoomes@2191: {
jcoomes@2191:   if (!ZapStackSegments) return;
jcoomes@2191:   const size_t zap_bytes = segment_bytes() - (zap_link_field ? 0 : sizeof(E*));
jcoomes@2191:   uint32_t* cur = (uint32_t*)seg;
jcoomes@2191:   const uint32_t* end = cur + zap_bytes / sizeof(uint32_t);
jcoomes@2191:   while (cur < end) {
jcoomes@2191:     *cur++ = 0xfadfaded;
jcoomes@2191:   }
jcoomes@2191: }
jcoomes@2191: #endif
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: E* ResourceStack<E>::alloc(size_t bytes)
jcoomes@2191: {
jcoomes@2191:   return (E*) resource_allocate_bytes(bytes);
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: void ResourceStack<E>::free(E* addr, size_t bytes)
jcoomes@2191: {
jcoomes@2191:   resource_free_bytes((char*) addr, bytes);
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: void StackIterator<E>::sync()
jcoomes@2191: {
jcoomes@2191:   _full_seg_size = _stack._full_seg_size;
jcoomes@2191:   _cur_seg_size = _stack._cur_seg_size;
jcoomes@2191:   _cur_seg = _stack._cur_seg;
jcoomes@2191: }
jcoomes@2191: 
jcoomes@2191: template <class E>
jcoomes@2191: E* StackIterator<E>::next_addr()
jcoomes@2191: {
jcoomes@2191:   assert(!is_empty(), "no items left");
jcoomes@2191:   if (_cur_seg_size == 1) {
jcoomes@2191:     E* addr = _cur_seg;
jcoomes@2191:     _cur_seg = _stack.get_link(_cur_seg);
jcoomes@2191:     _cur_seg_size = _stack.segment_size();
jcoomes@2191:     _full_seg_size -= _stack.segment_size();
jcoomes@2191:     return addr;
jcoomes@2191:   }
jcoomes@2191:   return _cur_seg + --_cur_seg_size;
jcoomes@2191: }