1 /* 2 * Copyright (c) 2013, 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 #include "precompiled.hpp" 26 #include "gc_implementation/g1/g1PreservedMarksQueue.hpp" 27 #include "memory/allocation.hpp" 28 #include "memory/allocation.inline.hpp" 29 #include "oops/oopsHierarchy.hpp" 30 31 class G1PreservedMarksChunk : public ResourceObj { 32 const size_t _capacity; 33 size_t _write_index; 34 size_t _read_index; 35 G1PreservedMarksQueueEntry* _data; 36 37 public: 38 G1PreservedMarksChunk(size_t capacity) : _capacity(capacity), _write_index(0), _read_index(0), _next(NULL) { 39 _data = NEW_C_HEAP_ARRAY(G1PreservedMarksQueueEntry, _capacity, mtGC); 40 } 41 42 ~G1PreservedMarksChunk() { 43 FREE_C_HEAP_ARRAY(G1PreservedMarksQueueEntry, _data, mtGC); 44 } 45 46 bool has_data() { 47 return _write_index > _read_index; 48 } 49 50 bool is_full() { 51 assert(_write_index <= _capacity, "written too far"); 52 return _write_index == _capacity; 53 } 54 55 void append(const G1PreservedMarksQueueEntry& entry) { 56 assert(!is_full(), "overflow"); 57 _data[_write_index++] = entry; 58 } 59 60 G1PreservedMarksQueueEntry remove_first() { 61 assert(has_data(), "empty"); 62 return _data[_read_index++]; 63 } 64 65 G1PreservedMarksChunk* _next; 66 }; 67 68 bool G1PreservedMarksQueue::has_data() { 69 return _current_read_chunk != NULL && _current_read_chunk->has_data(); 70 } 71 72 size_t G1PreservedMarksQueue::new_chunk_capacity() { 73 if (_current_write_chunk == NULL) { 74 _current_capacity = _initial_chunk_capacity; 75 } else if (_current_capacity == _max_chunk_capacity) { 76 // do nothing. already at max capacity 77 } else { 78 // Grow with 50%, similar to java.util.ArrayList 79 _current_capacity += _current_capacity >> 1; 80 _current_capacity = MIN2(_current_capacity, _max_chunk_capacity); 81 } 82 83 assert(_current_capacity >= _initial_chunk_capacity, "too small capacity"); assert(_current_capacity <= _max_chunk_capacity, "too large capacity"); 84 85 return _current_capacity; 86 } 87 88 G1PreservedMarksChunk* G1PreservedMarksQueue::new_chunk() { 89 return new (ResourceObj::C_HEAP, mtGC) G1PreservedMarksChunk(new_chunk_capacity()); 90 } 91 92 void G1PreservedMarksQueue::append(const oop& obj, const markOop& mark) { 93 G1PreservedMarksQueueEntry entry = {obj, mark}; 94 if (_current_write_chunk == NULL) { 95 assert(_current_read_chunk == NULL, "must be"); 96 _current_write_chunk = new_chunk(); 97 _current_read_chunk = _current_write_chunk; 98 } else if (_current_write_chunk->is_full()) { 99 G1PreservedMarksChunk* current_chunk = new_chunk(); 100 _current_write_chunk->_next = current_chunk; 101 _current_write_chunk = current_chunk; 102 } 103 104 assert(!_current_write_chunk->is_full(), "full"); 105 106 _current_write_chunk->append(entry); 107 } 108 109 G1PreservedMarksQueueEntry G1PreservedMarksQueue::remove_first() { 110 assert(has_data(), "empty"); 111 G1PreservedMarksQueueEntry entry = _current_read_chunk->remove_first(); 112 113 if (!_current_read_chunk->has_data()) { 114 G1PreservedMarksChunk* old_chunk = _current_read_chunk; 115 _current_read_chunk = old_chunk->_next; 116 117 if (old_chunk == _current_write_chunk) { 118 assert(_current_read_chunk == NULL, "we are deleting the last chunk"); 119 _current_write_chunk = NULL; 120 } 121 122 delete old_chunk; 123 } 124 125 return entry; 126 } 127 128 /////////////// Unit tests /////////////// 129 130 #ifndef PRODUCT 131 132 void g1PreservedMarksChunkTests() { 133 const int chunk_size = 5; 134 135 G1PreservedMarksChunk* chunk = new (ResourceObj::C_HEAP, mtGC) G1PreservedMarksChunk(chunk_size); 136 137 assert(!chunk->is_full(), ""); 138 assert(!chunk->has_data(), ""); 139 140 for (int i = 0; i < chunk_size; i++) { 141 G1PreservedMarksQueueEntry entry = {(oop)i, (markOop)(chunk_size - i)}; 142 chunk->append(entry); 143 } 144 145 assert(chunk->is_full(), ""); 146 assert(chunk->has_data(), ""); 147 148 for (int i = 0; i < chunk_size; i++) { 149 assert(chunk->has_data(), ""); 150 G1PreservedMarksQueueEntry entry = chunk->remove_first(); 151 assert((oop)i == entry.obj, ""); 152 assert((markOop)(chunk_size - i) == entry.mark, ""); 153 } 154 155 assert(chunk->is_full(), ""); 156 assert(!chunk->has_data(), ""); 157 158 delete chunk; 159 } 160 161 void G1PreservedMarksQueue::verify_empty() { 162 assert(_current_write_chunk == NULL, "_current_write_chunk not null"); 163 assert(_current_read_chunk == NULL, "_current_read_chunk not null"); 164 } 165 166 void g1PreserveMarkQueueUse(G1PreservedMarksQueue& queue) { 167 assert(!queue.has_data(), ""); 168 169 const int num_entries = 51; 170 for (int i = 0; i < num_entries; i++) { 171 queue.append((oop)i, (markOop)(num_entries - i)); 172 } 173 174 assert(queue.has_data(), ""); 175 176 for (int i = 0; i < num_entries; i++) { 177 assert(queue.has_data(), ""); 178 G1PreservedMarksQueueEntry entry = queue.remove_first(); 179 assert((oop)i == entry.obj, err_msg("wrong data (" PTR_FORMAT ") at index %d", (oopDesc*)(entry.obj), i)); 180 assert((markOop)(num_entries - i) == entry.mark, err_msg("wrong data (" PTR_FORMAT ") at index %d", entry.mark, i)); 181 } 182 183 assert(!queue.has_data(), ""); 184 185 queue.verify_empty(); 186 } 187 188 void g1PreserveMarkQueueTestOneUse() { 189 G1PreservedMarksQueue queue(5, 10); 190 g1PreserveMarkQueueUse(queue); 191 } 192 193 194 void g1PreserveMarkQueueTestMultiUse() { 195 G1PreservedMarksQueue queue(5, 10); 196 g1PreserveMarkQueueUse(queue); 197 g1PreserveMarkQueueUse(queue); 198 g1PreserveMarkQueueUse(queue); 199 } 200 201 void g1PreservedMarksQueueTests() { 202 g1PreserveMarkQueueTestOneUse(); 203 g1PreserveMarkQueueTestMultiUse(); 204 } 205 206 #endif 207 208