g1BlockOffsetTable.hpp revision 8413:92457dfb91bd
1141104Sharti/* 21590Srgrimes * Copyright (c) 2001, 2015, Oracle and/or its affiliates. All rights reserved. 31590Srgrimes * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 41590Srgrimes * 51590Srgrimes * This code is free software; you can redistribute it and/or modify it 61590Srgrimes * under the terms of the GNU General Public License version 2 only, as 71590Srgrimes * published by the Free Software Foundation. 81590Srgrimes * 91590Srgrimes * This code is distributed in the hope that it will be useful, but WITHOUT 101590Srgrimes * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 111590Srgrimes * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 121590Srgrimes * version 2 for more details (a copy is included in the LICENSE file that 131590Srgrimes * accompanied this code). 141590Srgrimes * 151590Srgrimes * You should have received a copy of the GNU General Public License version 161590Srgrimes * 2 along with this work; if not, write to the Free Software Foundation, 171590Srgrimes * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 181590Srgrimes * 191590Srgrimes * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 201590Srgrimes * or visit www.oracle.com if you need additional information or have any 211590Srgrimes * questions. 221590Srgrimes * 231590Srgrimes */ 241590Srgrimes 251590Srgrimes#ifndef SHARE_VM_GC_G1_G1BLOCKOFFSETTABLE_HPP 261590Srgrimes#define SHARE_VM_GC_G1_G1BLOCKOFFSETTABLE_HPP 271590Srgrimes 281590Srgrimes#include "gc/g1/g1RegionToSpaceMapper.hpp" 291590Srgrimes#include "memory/memRegion.hpp" 301590Srgrimes#include "memory/virtualspace.hpp" 311590Srgrimes#include "utilities/globalDefinitions.hpp" 321590Srgrimes 331590Srgrimes// The CollectedHeap type requires subtypes to implement a method 341590Srgrimes// "block_start". For some subtypes, notably generational 351590Srgrimes// systems using card-table-based write barriers, the efficiency of this 361590Srgrimes// operation may be important. Implementations of the "BlockOffsetArray" 3762833Swsanchez// class may be useful in providing such efficient implementations. 3862833Swsanchez// 391590Srgrimes// While generally mirroring the structure of the BOT for GenCollectedHeap, 401590Srgrimes// the following types are tailored more towards G1's uses; these should, 4162833Swsanchez// however, be merged back into a common BOT to avoid code duplication 4294587Sobrien// and reduce maintenance overhead. 431590Srgrimes// 441590Srgrimes// G1BlockOffsetTable (abstract) 451590Srgrimes// -- G1BlockOffsetArray (uses G1BlockOffsetSharedArray) 461590Srgrimes// -- G1BlockOffsetArrayContigSpace 471590Srgrimes// 481590Srgrimes// A main impediment to the consolidation of this code might be the 491590Srgrimes// effect of making some of the block_start*() calls non-const as 501590Srgrimes// below. Whether that might adversely affect performance optimizations 511590Srgrimes// that compilers might normally perform in the case of non-G1 521590Srgrimes// collectors needs to be carefully investigated prior to any such 531590Srgrimes// consolidation. 541590Srgrimes 551590Srgrimes// Forward declarations 561590Srgrimesclass G1BlockOffsetSharedArray; 571590Srgrimesclass G1OffsetTableContigSpace; 58126824Sru 59126824Sruclass G1BlockOffsetTable VALUE_OBJ_CLASS_SPEC { 60126824Sru friend class VMStructs; 611590Srgrimesprotected: 621590Srgrimes // These members describe the region covered by the table. 631590Srgrimes 641590Srgrimes // The space this table is covering. 651590Srgrimes HeapWord* _bottom; // == reserved.start 661590Srgrimes HeapWord* _end; // End of currently allocated region. 671590Srgrimes 681590Srgrimespublic: 691590Srgrimes // Initialize the table to cover the given space. 701590Srgrimes // The contents of the initial table are undefined. 711590Srgrimes G1BlockOffsetTable(HeapWord* bottom, HeapWord* end) : 721590Srgrimes _bottom(bottom), _end(end) 731590Srgrimes { 741590Srgrimes assert(_bottom <= _end, "arguments out of order"); 751590Srgrimes } 761590Srgrimes 771590Srgrimes // Note that the committed size of the covered space may have changed, 781590Srgrimes // so the table size might also wish to change. 791590Srgrimes virtual void resize(size_t new_word_size) = 0; 801590Srgrimes 811590Srgrimes virtual void set_bottom(HeapWord* new_bottom) { 821590Srgrimes assert(new_bottom <= _end, 831590Srgrimes err_msg("new_bottom (" PTR_FORMAT ") > _end (" PTR_FORMAT ")", 84141104Sharti p2i(new_bottom), p2i(_end))); 851590Srgrimes _bottom = new_bottom; 86141104Sharti resize(pointer_delta(_end, _bottom)); 87141104Sharti } 8827644Scharnier 89141104Sharti // Requires "addr" to be contained by a block, and returns the address of 90141104Sharti // the start of that block. (May have side effects, namely updating of 91141104Sharti // shared array entries that "point" too far backwards. This can occur, 92141104Sharti // for example, when LAB allocation is used in a space covered by the 93141104Sharti // table.) 941590Srgrimes virtual HeapWord* block_start_unsafe(const void* addr) = 0; 95141104Sharti // Same as above, but does not have any of the possible side effects 96141104Sharti // discussed above. 97141104Sharti virtual HeapWord* block_start_unsafe_const(const void* addr) const = 0; 981590Srgrimes 99141104Sharti // Returns the address of the start of the block containing "addr", or 100141104Sharti // else "null" if it is covered by no block. (May have side effects, 101141104Sharti // namely updating of shared array entries that "point" too far 1021590Srgrimes // backwards. This can occur, for example, when lab allocation is used 103141104Sharti // in a space covered by the table.) 104141104Sharti inline HeapWord* block_start(const void* addr); 105141104Sharti // Same as above, but does not have any of the possible side effects 106141104Sharti // discussed above. 107141104Sharti inline HeapWord* block_start_const(const void* addr) const; 1081590Srgrimes}; 1091590Srgrimes 1101590Srgrimesclass G1BlockOffsetSharedArrayMappingChangedListener : public G1MappingChangedListener { 1111590Srgrimes public: 1121590Srgrimes virtual void on_commit(uint start_idx, size_t num_regions, bool zero_filled) { 1131590Srgrimes // Nothing to do. The BOT is hard-wired to be part of the HeapRegion, and we cannot 1141590Srgrimes // retrieve it here since this would cause firing of several asserts. The code 1151590Srgrimes // executed after commit of a region already needs to do some re-initialization of 116138916Sharti // the HeapRegion, so we combine that. 117138916Sharti } 118138916Sharti}; 119138916Sharti 1201590Srgrimes// This implementation of "G1BlockOffsetTable" divides the covered region 1211590Srgrimes// into "N"-word subregions (where "N" = 2^"LogN". An array with an entry 1221590Srgrimes// for each such subregion indicates how far back one must go to find the 1231590Srgrimes// start of the chunk that includes the first word of the subregion. 1241590Srgrimes// 1251590Srgrimes// Each BlockOffsetArray is owned by a Space. However, the actual array 1261590Srgrimes// may be shared by several BlockOffsetArrays; this is useful 1271590Srgrimes// when a single resizable area (such as a generation) is divided up into 128132439Sharti// several spaces in which contiguous allocation takes place, 129126824Sru// such as, for example, in G1 or in the train generation.) 130138916Sharti 131138916Sharti// Here is the shared array type. 1321590Srgrimes 133138916Sharticlass G1BlockOffsetSharedArray: public CHeapObj<mtGC> { 134144020Sharti friend class G1BlockOffsetArray; 135138916Sharti friend class G1BlockOffsetArrayContigSpace; 136138916Sharti friend class VMStructs; 137144020Sharti 138138916Shartiprivate: 1391590Srgrimes G1BlockOffsetSharedArrayMappingChangedListener _listener; 1401590Srgrimes // The reserved region covered by the shared array. 1411590Srgrimes MemRegion _reserved; 1421590Srgrimes 1431590Srgrimes // End of the current committed region. 1441590Srgrimes HeapWord* _end; 1451590Srgrimes 1461590Srgrimes // Array for keeping offsets for retrieving object start fast given an 1471590Srgrimes // address. 1481590Srgrimes u_char* _offset_array; // byte array keeping backwards offsets 1491590Srgrimes 1501590Srgrimes void check_offset(size_t offset, const char* msg) const { 1511590Srgrimes assert(offset <= N_words, 1521590Srgrimes err_msg("%s - " 1531590Srgrimes "offset: " SIZE_FORMAT", N_words: %u", 1541590Srgrimes msg, offset, (uint)N_words)); 1551590Srgrimes } 1561590Srgrimes 1571590Srgrimes // Bounds checking accessors: 1581590Srgrimes // For performance these have to devolve to array accesses in product builds. 1591590Srgrimes inline u_char offset_array(size_t index) const; 1601590Srgrimes 16118730Ssteve void set_offset_array_raw(size_t index, u_char offset) { 1621590Srgrimes _offset_array[index] = offset; 16318730Ssteve } 16419344Ssteve 1651590Srgrimes inline void set_offset_array(size_t index, u_char offset); 1661590Srgrimes 1671590Srgrimes inline void set_offset_array(size_t index, HeapWord* high, HeapWord* low); 1681590Srgrimes 1691590Srgrimes inline void set_offset_array(size_t left, size_t right, u_char offset); 17018730Ssteve 1711590Srgrimes bool is_card_boundary(HeapWord* p) const; 1721590Srgrimes 1731590Srgrimes void check_index(size_t index, const char* msg) const NOT_DEBUG_RETURN; 1741590Srgrimes 17518730Sstevepublic: 1761590Srgrimes 1771590Srgrimes // Return the number of slots needed for an offset array 17869527Swill // that covers mem_region_words words. 1791590Srgrimes static size_t compute_size(size_t mem_region_words) { 1801590Srgrimes size_t number_of_slots = (mem_region_words / N_words); 1811590Srgrimes return ReservedSpace::allocation_align_size_up(number_of_slots); 1821590Srgrimes } 1831590Srgrimes 1841590Srgrimes // Returns how many bytes of the heap a single byte of the BOT corresponds to. 1851590Srgrimes static size_t heap_map_factor() { 1861590Srgrimes return N_bytes; 1871590Srgrimes } 1881590Srgrimes 1891590Srgrimes enum SomePublicConstants { 1901590Srgrimes LogN = 9, 191141252Sharti LogN_words = LogN - LogHeapWordSize, 1921590Srgrimes N_bytes = 1 << LogN, 1931590Srgrimes N_words = 1 << LogN_words 1941590Srgrimes }; 1951590Srgrimes 1961590Srgrimes // Initialize the table to cover from "base" to (at least) 1971590Srgrimes // "base + init_word_size". In the future, the table may be expanded 1981590Srgrimes // (see "resize" below) up to the size of "_reserved" (which must be at 1991590Srgrimes // least "init_word_size".) The contents of the initial table are 2001590Srgrimes // undefined; it is the responsibility of the constituent 2011590Srgrimes // G1BlockOffsetTable(s) to initialize cards. 2021590Srgrimes G1BlockOffsetSharedArray(MemRegion heap, G1RegionToSpaceMapper* storage); 2031590Srgrimes 2041590Srgrimes // Return the appropriate index into "_offset_array" for "p". 2051590Srgrimes inline size_t index_for(const void* p) const; 2061590Srgrimes inline size_t index_for_raw(const void* p) const; 2071590Srgrimes 2081590Srgrimes // Return the address indicating the start of the region corresponding to 2091590Srgrimes // "index" in "_offset_array". 2101590Srgrimes inline HeapWord* address_for_index(size_t index) const; 21118730Ssteve // Variant of address_for_index that does not check the index for validity. 2121590Srgrimes inline HeapWord* address_for_index_raw(size_t index) const { 2139254Sache return _reserved.start() + (index << LogN_words); 2141590Srgrimes } 21518730Ssteve}; 2161590Srgrimes 21718730Ssteve// And here is the G1BlockOffsetTable subtype that uses the array. 21819344Ssteve 2191590Srgrimesclass G1BlockOffsetArray: public G1BlockOffsetTable { 2201590Srgrimes friend class G1BlockOffsetSharedArray; 2211590Srgrimes friend class G1BlockOffsetArrayContigSpace; 2221590Srgrimes friend class VMStructs; 2231590Srgrimesprivate: 2241590Srgrimes enum SomePrivateConstants { 2251590Srgrimes N_words = G1BlockOffsetSharedArray::N_words, 22618730Ssteve LogN = G1BlockOffsetSharedArray::LogN 2271590Srgrimes }; 2281590Srgrimes 22992921Simp // This is the array, which can be shared by several BlockOffsetArray's 230138512Sharti // servicing different 23192921Simp G1BlockOffsetSharedArray* _array; 23292921Simp 23392921Simp // The space that owns this subregion. 23492921Simp G1OffsetTableContigSpace* _gsp; 23592921Simp 23692921Simp // The portion [_unallocated_block, _sp.end()) of the space that 237128160Sru // is a single block known not to contain any objects. 2381590Srgrimes // NOTE: See BlockOffsetArrayUseUnallocatedBlock flag. 23992921Simp HeapWord* _unallocated_block; 2401590Srgrimes 24192921Simp // Sets the entries 24292921Simp // corresponding to the cards starting at "start" and ending at "end" 243126824Sru // to point back to the card before "start": the interval [start, end) 24492921Simp // is right-open. 2451590Srgrimes void set_remainder_to_point_to_start(HeapWord* start, HeapWord* end); 2461590Srgrimes // Same as above, except that the args here are a card _index_ interval 2471590Srgrimes // that is closed: [start_index, end_index] 2481590Srgrimes void set_remainder_to_point_to_start_incl(size_t start, size_t end); 2491590Srgrimes 2501590Srgrimesprotected: 2511590Srgrimes 2521590Srgrimes G1OffsetTableContigSpace* gsp() const { return _gsp; } 2531590Srgrimes 2541590Srgrimes inline size_t block_size(const HeapWord* p) const; 2551590Srgrimes 2561590Srgrimes // Returns the address of a block whose start is at most "addr". 2571590Srgrimes // If "has_max_index" is true, "assumes "max_index" is the last valid one 2581590Srgrimes // in the array. 259138232Sharti inline HeapWord* block_at_or_preceding(const void* addr, 2601590Srgrimes bool has_max_index, 26194584Sobrien size_t max_index) const; 2621590Srgrimes 2631590Srgrimes // "q" is a block boundary that is <= "addr"; "n" is the address of the 26494584Sobrien // next block (or the end of the space.) Return the address of the 2658874Srgrimes // beginning of the block that contains "addr". Does so without side 2661590Srgrimes // effects (see, e.g., spec of block_start.) 267138232Sharti inline HeapWord* 2681590Srgrimes forward_to_block_containing_addr_const(HeapWord* q, HeapWord* n, 2691590Srgrimes const void* addr) const; 2701590Srgrimes 271138232Sharti // "q" is a block boundary that is <= "addr"; return the address of the 2721590Srgrimes // beginning of the block that contains "addr". May have side effects 2731590Srgrimes // on "this", by updating imprecise entries. 2741590Srgrimes inline HeapWord* forward_to_block_containing_addr(HeapWord* q, 2751590Srgrimes const void* addr); 2761590Srgrimes 2771590Srgrimes // "q" is a block boundary that is <= "addr"; "n" is the address of the 2781590Srgrimes // next block (or the end of the space.) Return the address of the 2791590Srgrimes // beginning of the block that contains "addr". May have side effects 2801590Srgrimes // on "this", by updating imprecise entries. 2811590Srgrimes HeapWord* forward_to_block_containing_addr_slow(HeapWord* q, 2821590Srgrimes HeapWord* n, 2831590Srgrimes const void* addr); 2841590Srgrimes 2851590Srgrimes // Requires that "*threshold_" be the first array entry boundary at or 2861590Srgrimes // above "blk_start", and that "*index_" be the corresponding array 2871590Srgrimes // index. If the block starts at or crosses "*threshold_", records 2881590Srgrimes // "blk_start" as the appropriate block start for the array index 2891590Srgrimes // starting at "*threshold_", and for any other indices crossed by the 2901590Srgrimes // block. Updates "*threshold_" and "*index_" to correspond to the first 2911590Srgrimes // index after the block end. 2921590Srgrimes void alloc_block_work2(HeapWord** threshold_, size_t* index_, 2931590Srgrimes HeapWord* blk_start, HeapWord* blk_end); 2941590Srgrimes 2951590Srgrimespublic: 2961590Srgrimes // The space may not have it's bottom and top set yet, which is why the 2971590Srgrimes // region is passed as a parameter. The elements of the array are 29898136Sjmallett // initialized to zero. 2991590Srgrimes G1BlockOffsetArray(G1BlockOffsetSharedArray* array, MemRegion mr); 3001590Srgrimes 30193056Simp // Note: this ought to be part of the constructor, but that would require 3021590Srgrimes // "this" to be passed as a parameter to a member constructor for 303138232Sharti // the containing concrete subtype of Space. 304126824Sru // This would be legal C++, but MS VC++ doesn't allow it. 3051590Srgrimes void set_space(G1OffsetTableContigSpace* sp); 306138232Sharti 307138232Sharti // Resets the covered region to one with the same _bottom as before but 3081590Srgrimes // the "new_word_size". 309138232Sharti void resize(size_t new_word_size); 310138232Sharti 3111590Srgrimes virtual HeapWord* block_start_unsafe(const void* addr); 3121590Srgrimes virtual HeapWord* block_start_unsafe_const(const void* addr) const; 3131590Srgrimes 3141590Srgrimes void check_all_cards(size_t left_card, size_t right_card) const; 3151590Srgrimes 3161590Srgrimes void verify() const; 3171590Srgrimes 318143100Sharti virtual void print_on(outputStream* out) PRODUCT_RETURN; 3191590Srgrimes}; 3201590Srgrimes 3211590Srgrimes// A subtype of BlockOffsetArray that takes advantage of the fact 3221590Srgrimes// that its underlying space is a ContiguousSpace, so that its "active" 323143100Sharti// region can be more efficiently tracked (than for a non-contiguous space). 3241590Srgrimesclass G1BlockOffsetArrayContigSpace: public G1BlockOffsetArray { 3251590Srgrimes friend class VMStructs; 3261590Srgrimes 3271590Srgrimes // allocation boundary at which offset array must be updated 328143027Sharti HeapWord* _next_offset_threshold; 329143027Sharti size_t _next_offset_index; // index corresponding to that boundary 3301590Srgrimes 331143027Sharti // Work function to be called when allocation start crosses the next 332143027Sharti // threshold in the contig space. 333138232Sharti void alloc_block_work1(HeapWord* blk_start, HeapWord* blk_end) { 334143027Sharti alloc_block_work2(&_next_offset_threshold, &_next_offset_index, 335143027Sharti blk_start, blk_end); 336143027Sharti } 337143027Sharti 338143027Sharti // Zero out the entry for _bottom (offset will be zero). Does not check for availability of the 339143027Sharti // memory first. 340143027Sharti void zero_bottom_entry_raw(); 341143027Sharti // Variant of initialize_threshold that does not check for availability of the 342143027Sharti // memory first. 3431590Srgrimes HeapWord* initialize_threshold_raw(); 3441590Srgrimes public: 3451590Srgrimes G1BlockOffsetArrayContigSpace(G1BlockOffsetSharedArray* array, MemRegion mr); 3461590Srgrimes 3471590Srgrimes // Initialize the threshold to reflect the first boundary after the 3481590Srgrimes // bottom of the covered region. 349143684Sharti HeapWord* initialize_threshold(); 350143684Sharti 351143684Sharti void reset_bot() { 352143684Sharti zero_bottom_entry_raw(); 3531590Srgrimes initialize_threshold_raw(); 3541590Srgrimes } 3551590Srgrimes 3561590Srgrimes // Return the next threshold, the point at which the table should be 3571590Srgrimes // updated. 3581590Srgrimes HeapWord* threshold() const { return _next_offset_threshold; } 359143684Sharti 360143684Sharti // These must be guaranteed to work properly (i.e., do nothing) 3611590Srgrimes // when "blk_start" ("blk" for second version) is "NULL". In this 362143684Sharti // implementation, that's true because NULL is represented as 0, and thus 363143684Sharti // never exceeds the "_next_offset_threshold". 364143684Sharti void alloc_block(HeapWord* blk_start, HeapWord* blk_end) { 365138232Sharti if (blk_end > _next_offset_threshold) 366143684Sharti alloc_block_work1(blk_start, blk_end); 367143684Sharti } 3681590Srgrimes void alloc_block(HeapWord* blk, size_t size) { 369143684Sharti alloc_block(blk, blk+size); 370143684Sharti } 371143684Sharti 372143684Sharti HeapWord* block_start_unsafe(const void* addr); 373143684Sharti HeapWord* block_start_unsafe_const(const void* addr) const; 374143684Sharti 375143684Sharti void set_for_starts_humongous(HeapWord* new_top); 376143684Sharti 377143684Sharti virtual void print_on(outputStream* out) PRODUCT_RETURN; 378143684Sharti}; 379143684Sharti 380143684Sharti#endif // SHARE_VM_GC_G1_G1BLOCKOFFSETTABLE_HPP 3818874Srgrimes