#ifndef SHARE_VM_GC_IMPLEMENTATION_G1_G1BLOCKOFFSETTABLE_HPP

#define SHARE_VM_GC_IMPLEMENTATION_G1_G1BLOCKOFFSETTABLE_HPP

#include "memory/memRegion.hpp"

#include "runtime/virtualspace.hpp"

#include "utilities/globalDefinitions.hpp"

class ContiguousSpace;

class G1BlockOffsetSharedArray;

class G1BlockOffsetTable VALUE_OBJ_CLASS_SPEC {

friend class VMStructs;

protected:

// These members describe the region covered by the table.

// The space this table is covering.

HeapWord* _bottom; // == reserved.start

HeapWord* _end; // End of currently allocated region.

public:

// Initialize the table to cover the given space.

// The contents of the initial table are undefined.

G1BlockOffsetTable(HeapWord* bottom, HeapWord* end) :

_bottom(bottom), _end(end)

{

assert(_bottom <= _end, "arguments out of order");

}

// Note that the committed size of the covered space may have changed,

// so the table size might also wish to change.

virtual void resize(size_t new_word_size) = 0;

virtual void set_bottom(HeapWord* new_bottom) {

assert(new_bottom <= _end,

err_msg("new_bottom (" PTR_FORMAT ") > _end (" PTR_FORMAT ")",

new_bottom, _end));

_bottom = new_bottom;

resize(pointer_delta(_end, _bottom));

}

// Requires "addr" to be contained by a block, and returns the address of

// the start of that block. (May have side effects, namely updating of

// shared array entries that "point" too far backwards. This can occur,

// for example, when LAB allocation is used in a space covered by the

// table.)

virtual HeapWord* block_start_unsafe(const void* addr) = 0;

// Same as above, but does not have any of the possible side effects

// discussed above.

virtual HeapWord* block_start_unsafe_const(const void* addr) const = 0;

// Returns the address of the start of the block containing "addr", or

// else "null" if it is covered by no block. (May have side effects,

// namely updating of shared array entries that "point" too far

// backwards. This can occur, for example, when lab allocation is used

// in a space covered by the table.)

inline HeapWord* block_start(const void* addr);

// Same as above, but does not have any of the possible side effects

// discussed above.

inline HeapWord* block_start_const(const void* addr) const;

};

class G1BlockOffsetSharedArray: public CHeapObj<mtGC> {

friend class G1BlockOffsetArray;

friend class G1BlockOffsetArrayContigSpace;

friend class VMStructs;

private:

// The reserved region covered by the shared array.

MemRegion _reserved;

// End of the current committed region.

HeapWord* _end;

// Array for keeping offsets for retrieving object start fast given an

// address.

VirtualSpace _vs;

u_char* _offset_array; // byte array keeping backwards offsets

void check_index(size_t index, const char* msg) const {

assert(index < _vs.committed_size(),

err_msg("%s - "

"index: " SIZE_FORMAT ", _vs.committed_size: " SIZE_FORMAT,

msg, index, _vs.committed_size()));

}

void check_offset(size_t offset, const char* msg) const {

assert(offset <= N_words,

err_msg("%s - "

"offset: " UINT32_FORMAT", N_words: " UINT32_FORMAT,

msg, offset, N_words));

}

// Bounds checking accessors:

// For performance these have to devolve to array accesses in product builds.

u_char offset_array(size_t index) const {

check_index(index, "index out of range");

return _offset_array[index];

}

void set_offset_array(size_t index, u_char offset) {

check_index(index, "index out of range");

check_offset(offset, "offset too large");

_offset_array[index] = offset;

}

void set_offset_array(size_t index, HeapWord* high, HeapWord* low) {

check_index(index, "index out of range");

assert(high >= low, "addresses out of order");

check_offset(pointer_delta(high, low), "offset too large");

_offset_array[index] = (u_char) pointer_delta(high, low);

}

void set_offset_array(HeapWord* left, HeapWord* right, u_char offset) {

check_index(index_for(right - 1), "right address out of range");

assert(left < right, "Heap addresses out of order");

size_t num_cards = pointer_delta(right, left) >> LogN_words;

if (UseMemSetInBOT) {

memset(&_offset_array[index_for(left)], offset, num_cards);

} else {

size_t i = index_for(left);

const size_t end = i + num_cards;

for (; i < end; i++) {

_offset_array[i] = offset;

}

}

}

void set_offset_array(size_t left, size_t right, u_char offset) {

check_index(right, "right index out of range");

assert(left <= right, "indexes out of order");

size_t num_cards = right - left + 1;

if (UseMemSetInBOT) {

memset(&_offset_array[left], offset, num_cards);

} else {

size_t i = left;

const size_t end = i + num_cards;

for (; i < end; i++) {

_offset_array[i] = offset;

}

}

}

void check_offset_array(size_t index, HeapWord* high, HeapWord* low) const {

check_index(index, "index out of range");

assert(high >= low, "addresses out of order");

check_offset(pointer_delta(high, low), "offset too large");

assert(_offset_array[index] == pointer_delta(high, low), "Wrong offset");

}

bool is_card_boundary(HeapWord* p) const;

// Return the number of slots needed for an offset array

// that covers mem_region_words words.

// We always add an extra slot because if an object

// ends on a card boundary we put a 0 in the next

// offset array slot, so we want that slot always

// to be reserved.

size_t compute_size(size_t mem_region_words) {

size_t number_of_slots = (mem_region_words / N_words) + 1;

return ReservedSpace::page_align_size_up(number_of_slots);

}

public:

enum SomePublicConstants {

LogN = 9,

LogN_words = LogN - LogHeapWordSize,

N_bytes = 1 << LogN,

N_words = 1 << LogN_words

};

// Initialize the table to cover from "base" to (at least)

// "base + init_word_size". In the future, the table may be expanded

// (see "resize" below) up to the size of "_reserved" (which must be at

// least "init_word_size".) The contents of the initial table are

// undefined; it is the responsibility of the constituent

// G1BlockOffsetTable(s) to initialize cards.

G1BlockOffsetSharedArray(MemRegion reserved, size_t init_word_size);

// Notes a change in the committed size of the region covered by the

// table. The "new_word_size" may not be larger than the size of the

// reserved region this table covers.

void resize(size_t new_word_size);

void set_bottom(HeapWord* new_bottom);

// Updates all the BlockOffsetArray's sharing this shared array to

// reflect the current "top"'s of their spaces.

void update_offset_arrays();

// Return the appropriate index into "_offset_array" for "p".

inline size_t index_for(const void* p) const;

// Return the address indicating the start of the region corresponding to

// "index" in "_offset_array".

inline HeapWord* address_for_index(size_t index) const;

};

class G1BlockOffsetArray: public G1BlockOffsetTable {

friend class G1BlockOffsetSharedArray;

friend class G1BlockOffsetArrayContigSpace;

friend class VMStructs;

private:

enum SomePrivateConstants {

N_words = G1BlockOffsetSharedArray::N_words,

LogN = G1BlockOffsetSharedArray::LogN

};

// The following enums are used by do_block_helper

enum Action {

Action_single, // BOT records a single block (see single_block())

Action_mark, // BOT marks the start of a block (see mark_block())

Action_check // Check that BOT records block correctly

// (see verify_single_block()).

};

// This is the array, which can be shared by several BlockOffsetArray's

// servicing different

G1BlockOffsetSharedArray* _array;

// The space that owns this subregion.

Space* _sp;

// If "_sp" is a contiguous space, the field below is the view of "_sp"

// as a contiguous space, else NULL.

ContiguousSpace* _csp;

// If true, array entries are initialized to 0; otherwise, they are

// initialized to point backwards to the beginning of the covered region.

bool _init_to_zero;

// The portion [_unallocated_block, _sp.end()) of the space that

// is a single block known not to contain any objects.

// NOTE: See BlockOffsetArrayUseUnallocatedBlock flag.

HeapWord* _unallocated_block;

// Sets the entries

// corresponding to the cards starting at "start" and ending at "end"

// to point back to the card before "start": the interval [start, end)

// is right-open.

void set_remainder_to_point_to_start(HeapWord* start, HeapWord* end);

// Same as above, except that the args here are a card _index_ interval

// that is closed: [start_index, end_index]

void set_remainder_to_point_to_start_incl(size_t start, size_t end);

// A helper function for BOT adjustment/verification work

void do_block_internal(HeapWord* blk_start, HeapWord* blk_end, Action action);

protected:

ContiguousSpace* csp() const { return _csp; }

// Returns the address of a block whose start is at most "addr".

// If "has_max_index" is true, "assumes "max_index" is the last valid one

// in the array.

inline HeapWord* block_at_or_preceding(const void* addr,

bool has_max_index,

size_t max_index) const;

// "q" is a block boundary that is <= "addr"; "n" is the address of the

// next block (or the end of the space.) Return the address of the

// beginning of the block that contains "addr". Does so without side

// effects (see, e.g., spec of block_start.)

inline HeapWord*

forward_to_block_containing_addr_const(HeapWord* q, HeapWord* n,

const void* addr) const;

// "q" is a block boundary that is <= "addr"; return the address of the

// beginning of the block that contains "addr". May have side effects

// on "this", by updating imprecise entries.

inline HeapWord* forward_to_block_containing_addr(HeapWord* q,

const void* addr);

// "q" is a block boundary that is <= "addr"; "n" is the address of the

// next block (or the end of the space.) Return the address of the

// beginning of the block that contains "addr". May have side effects

// on "this", by updating imprecise entries.

HeapWord* forward_to_block_containing_addr_slow(HeapWord* q,

HeapWord* n,

const void* addr);

// Requires that "*threshold_" be the first array entry boundary at or

// above "blk_start", and that "*index_" be the corresponding array

// index. If the block starts at or crosses "*threshold_", records

// "blk_start" as the appropriate block start for the array index

// starting at "*threshold_", and for any other indices crossed by the

// block. Updates "*threshold_" and "*index_" to correspond to the first

// index after the block end.

void alloc_block_work2(HeapWord** threshold_, size_t* index_,

HeapWord* blk_start, HeapWord* blk_end);

public:

// The space may not have it's bottom and top set yet, which is why the

// region is passed as a parameter. If "init_to_zero" is true, the

// elements of the array are initialized to zero. Otherwise, they are

// initialized to point backwards to the beginning.

G1BlockOffsetArray(G1BlockOffsetSharedArray* array, MemRegion mr,

bool init_to_zero);

// Note: this ought to be part of the constructor, but that would require

// "this" to be passed as a parameter to a member constructor for

// the containing concrete subtype of Space.

// This would be legal C++, but MS VC++ doesn't allow it.

void set_space(Space* sp);

// Resets the covered region to the given "mr".

void set_region(MemRegion mr);

// Resets the covered region to one with the same _bottom as before but

// the "new_word_size".

void resize(size_t new_word_size);

// These must be guaranteed to work properly (i.e., do nothing)

// when "blk_start" ("blk" for second version) is "NULL".

virtual void alloc_block(HeapWord* blk_start, HeapWord* blk_end);

virtual void alloc_block(HeapWord* blk, size_t size) {

alloc_block(blk, blk + size);

}

// The following methods are useful and optimized for a

// general, non-contiguous space.

// Given a block [blk_start, blk_start + full_blk_size), and

// a left_blk_size < full_blk_size, adjust the BOT to show two

// blocks [blk_start, blk_start + left_blk_size) and

// [blk_start + left_blk_size, blk_start + full_blk_size).

// It is assumed (and verified in the non-product VM) that the

// BOT was correct for the original block.

void split_block(HeapWord* blk_start, size_t full_blk_size,

size_t left_blk_size);

// Adjust the BOT to show that it has a single block in the

// range [blk_start, blk_start + size). All necessary BOT

// cards are adjusted, but _unallocated_block isn't.

void single_block(HeapWord* blk_start, HeapWord* blk_end);

void single_block(HeapWord* blk, size_t size) {

single_block(blk, blk + size);

}

// Adjust BOT to show that it has a block in the range

// [blk_start, blk_start + size). Only the first card

// of BOT is touched. It is assumed (and verified in the

// non-product VM) that the remaining cards of the block

// are correct.

void mark_block(HeapWord* blk_start, HeapWord* blk_end);

void mark_block(HeapWord* blk, size_t size) {

mark_block(blk, blk + size);

}

// Adjust _unallocated_block to indicate that a particular

// block has been newly allocated or freed. It is assumed (and

// verified in the non-product VM) that the BOT is correct for

// the given block.

inline void allocated(HeapWord* blk_start, HeapWord* blk_end) {

// Verify that the BOT shows [blk, blk + blk_size) to be one block.

verify_single_block(blk_start, blk_end);

if (BlockOffsetArrayUseUnallocatedBlock) {

_unallocated_block = MAX2(_unallocated_block, blk_end);

}

}

inline void allocated(HeapWord* blk, size_t size) {

allocated(blk, blk + size);

}

inline void freed(HeapWord* blk_start, HeapWord* blk_end);

inline void freed(HeapWord* blk, size_t size);

virtual HeapWord* block_start_unsafe(const void* addr);

virtual HeapWord* block_start_unsafe_const(const void* addr) const;

// Requires "addr" to be the start of a card and returns the

// start of the block that contains the given address.

HeapWord* block_start_careful(const void* addr) const;

// If true, initialize array slots with no allocated blocks to zero.

// Otherwise, make them point back to the front.

bool init_to_zero() { return _init_to_zero; }

// Verification & debugging - ensure that the offset table reflects the fact

// that the block [blk_start, blk_end) or [blk, blk + size) is a

// single block of storage. NOTE: can;t const this because of

// call to non-const do_block_internal() below.

inline void verify_single_block(HeapWord* blk_start, HeapWord* blk_end) {

if (VerifyBlockOffsetArray) {

do_block_internal(blk_start, blk_end, Action_check);

}

}

inline void verify_single_block(HeapWord* blk, size_t size) {

verify_single_block(blk, blk + size);

}

// Used by region verification. Checks that the contents of the

// BOT reflect that there's a single object that spans the address

// range [obj_start, obj_start + word_size); returns true if this is

// the case, returns false if it's not.

bool verify_for_object(HeapWord* obj_start, size_t word_size) const;

// Verify that the given block is before _unallocated_block

inline void verify_not_unallocated(HeapWord* blk_start,

HeapWord* blk_end) const {

if (BlockOffsetArrayUseUnallocatedBlock) {

assert(blk_start < blk_end, "Block inconsistency?");

assert(blk_end <= _unallocated_block, "_unallocated_block problem");

}

}

inline void verify_not_unallocated(HeapWord* blk, size_t size) const {

verify_not_unallocated(blk, blk + size);

}

void check_all_cards(size_t left_card, size_t right_card) const;

virtual void print_on(outputStream* out) PRODUCT_RETURN;

};

class G1BlockOffsetArrayContigSpace: public G1BlockOffsetArray {

friend class VMStructs;

// allocation boundary at which offset array must be updated

HeapWord* _next_offset_threshold;

size_t _next_offset_index; // index corresponding to that boundary

// Work function to be called when allocation start crosses the next

// threshold in the contig space.

void alloc_block_work1(HeapWord* blk_start, HeapWord* blk_end) {

alloc_block_work2(&_next_offset_threshold, &_next_offset_index,

blk_start, blk_end);

}

public:

G1BlockOffsetArrayContigSpace(G1BlockOffsetSharedArray* array, MemRegion mr);

// Initialize the threshold to reflect the first boundary after the

// bottom of the covered region.

HeapWord* initialize_threshold();

// Zero out the entry for _bottom (offset will be zero).

void zero_bottom_entry();

// Return the next threshold, the point at which the table should be

// updated.

HeapWord* threshold() const { return _next_offset_threshold; }

// These must be guaranteed to work properly (i.e., do nothing)

// when "blk_start" ("blk" for second version) is "NULL". In this

// implementation, that's true because NULL is represented as 0, and thus

// never exceeds the "_next_offset_threshold".

void alloc_block(HeapWord* blk_start, HeapWord* blk_end) {

if (blk_end > _next_offset_threshold)

alloc_block_work1(blk_start, blk_end);

}

void alloc_block(HeapWord* blk, size_t size) {

alloc_block(blk, blk+size);

}

HeapWord* block_start_unsafe(const void* addr);

HeapWord* block_start_unsafe_const(const void* addr) const;

void set_for_starts_humongous(HeapWord* new_top);

virtual void print_on(outputStream* out) PRODUCT_RETURN;

};

#endif // SHARE_VM_GC_IMPLEMENTATION_G1_G1BLOCKOFFSETTABLE_HPP