/*

 * Copyright 1997-2007 Sun Microsystems, Inc.  All Rights Reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

// A space is an abstraction for the "storage units" backing

// up the generation abstraction. It includes specific

// implementations for keeping track of free and used space,

// for iterating over objects and free blocks, etc.

// Here's the Space hierarchy:

//

// - Space               -- an asbtract base class describing a heap area

//   - CompactibleSpace  -- a space supporting compaction

//     - CompactibleFreeListSpace -- (used for CMS generation)

//     - ContiguousSpace -- a compactible space in which all free space

//                          is contiguous

//       - EdenSpace     -- contiguous space used as nursery

//         - ConcEdenSpace -- contiguous space with a 'soft end safe' allocation

//       - OffsetTableContigSpace -- contiguous space with a block offset array

//                          that allows "fast" block_start calls

//         - TenuredSpace -- (used for TenuredGeneration)

//         - ContigPermSpace -- an offset table contiguous space for perm gen

// Forward decls.

class Space;

class BlockOffsetArray;

class BlockOffsetArrayContigSpace;

class Generation;

class CompactibleSpace;

class BlockOffsetTable;

class GenRemSet;

class CardTableRS;

class DirtyCardToOopClosure;

// An oop closure that is circumscribed by a filtering memory region.

class SpaceMemRegionOopsIterClosure: public virtual OopClosure {

  OopClosure* cl;

  MemRegion mr;

public:

  void do_oop(oop* p) {

    if (mr.contains(p)) {

      cl->do_oop(p);

    }

  }

  SpaceMemRegionOopsIterClosure(OopClosure* _cl, MemRegion _mr): cl(_cl), mr(_mr) {}

};

// A Space describes a heap area. Class Space is an abstract

// base class.

//

// Space supports allocation, size computation and GC support is provided.

//

// Invariant: bottom() and end() are on page_size boundaries and

// bottom() <= top() <= end()

// top() is inclusive and end() is exclusive.

class Space: public CHeapObj {

  friend class VMStructs;

 protected:

  HeapWord* _bottom;

  HeapWord* _end;

  // Used in support of save_marks()

  HeapWord* _saved_mark_word;

  MemRegionClosure* _preconsumptionDirtyCardClosure;

  // A sequential tasks done structure. This supports

  // parallel GC, where we have threads dynamically

  // claiming sub-tasks from a larger parallel task.

  SequentialSubTasksDone _par_seq_tasks;

  Space():

    _bottom(NULL), _end(NULL), _preconsumptionDirtyCardClosure(NULL) { }

 public:

  // Accessors

  HeapWord* bottom() const         { return _bottom; }

  HeapWord* end() const            { return _end;    }

  virtual void set_bottom(HeapWord* value) { _bottom = value; }

  virtual void set_end(HeapWord* value)    { _end = value; }

  HeapWord* saved_mark_word() const  { return _saved_mark_word; }

  void set_saved_mark_word(HeapWord* p) { _saved_mark_word = p; }

  MemRegionClosure* preconsumptionDirtyCardClosure() const {

    return _preconsumptionDirtyCardClosure;

  }

  void setPreconsumptionDirtyCardClosure(MemRegionClosure* cl) {

    _preconsumptionDirtyCardClosure = cl;

  }

  // Returns a subregion of the space containing all the objects in

  // the space.

  virtual MemRegion used_region() const { return MemRegion(bottom(), end()); }

  // Returns a region that is guaranteed to contain (at least) all objects

  // allocated at the time of the last call to "save_marks".  If the space

  // initializes its DirtyCardToOopClosure's specifying the "contig" option

  // (that is, if the space is contiguous), then this region must contain only

  // such objects: the memregion will be from the bottom of the region to the

  // saved mark.  Otherwise, the "obj_allocated_since_save_marks" method of

  // the space must distiguish between objects in the region allocated before

  // and after the call to save marks.

  virtual MemRegion used_region_at_save_marks() const {

    return MemRegion(bottom(), saved_mark_word());

  }

  // Initialization

  virtual void initialize(MemRegion mr, bool clear_space);

  virtual void clear();

  // For detecting GC bugs.  Should only be called at GC boundaries, since

  // some unused space may be used as scratch space during GC's.

  // Default implementation does nothing. We also call this when expanding

  // a space to satisfy an allocation request. See bug #4668531

  virtual void mangle_unused_area() {}

  virtual void mangle_region(MemRegion mr) {}

  // Testers

  bool is_empty() const              { return used() == 0; }

  bool not_empty() const             { return used() > 0; }

  // Returns true iff the given the space contains the

  // given address as part of an allocated object. For

  // ceratin kinds of spaces, this might be a potentially

  // expensive operation. To prevent performance problems

  // on account of its inadvertent use in product jvm's,

  // we restrict its use to assertion checks only.

  virtual bool is_in(const void* p) const;

  // Returns true iff the given reserved memory of the space contains the

  // given address.

  bool is_in_reserved(const void* p) const { return _bottom <= p && p < _end; }

  // Returns true iff the given block is not allocated.

  virtual bool is_free_block(const HeapWord* p) const = 0;

  // Test whether p is double-aligned

  static bool is_aligned(void* p) {

    return ((intptr_t)p & (sizeof(double)-1)) == 0;

  }

  // Size computations.  Sizes are in bytes.

  size_t capacity()     const { return byte_size(bottom(), end()); }

  virtual size_t used() const = 0;

  virtual size_t free() const = 0;

  // Iterate over all the ref-containing fields of all objects in the

  // space, calling "cl.do_oop" on each.  Fields in objects allocated by

  // applications of the closure are not included in the iteration.

  virtual void oop_iterate(OopClosure* cl);

  // Same as above, restricted to the intersection of a memory region and

  // the space.  Fields in objects allocated by applications of the closure

  // are not included in the iteration.

  virtual void oop_iterate(MemRegion mr, OopClosure* cl) = 0;

  // Iterate over all objects in the space, calling "cl.do_object" on

  // each.  Objects allocated by applications of the closure are not

  // included in the iteration.

  virtual void object_iterate(ObjectClosure* blk) = 0;

  // Iterate over all objects that intersect with mr, calling "cl->do_object"

  // on each.  There is an exception to this: if this closure has already

  // been invoked on an object, it may skip such objects in some cases.  This is

  // Most likely to happen in an "upwards" (ascending address) iteration of

  // MemRegions.

  virtual void object_iterate_mem(MemRegion mr, UpwardsObjectClosure* cl);

  // Iterate over as many initialized objects in the space as possible,

  // calling "cl.do_object_careful" on each. Return NULL if all objects

  // in the space (at the start of the iteration) were iterated over.

  // Return an address indicating the extent of the iteration in the

  // event that the iteration had to return because of finding an

  // uninitialized object in the space, or if the closure "cl"

  // signalled early termination.

  virtual HeapWord* object_iterate_careful(ObjectClosureCareful* cl);

  virtual HeapWord* object_iterate_careful_m(MemRegion mr,

                                             ObjectClosureCareful* cl);

  // Create and return a new dirty card to oop closure. Can be

  // overriden to return the appropriate type of closure

  // depending on the type of space in which the closure will

  // operate. ResourceArea allocated.

  virtual DirtyCardToOopClosure* new_dcto_cl(OopClosure* cl,

                                             CardTableModRefBS::PrecisionStyle precision,

                                             HeapWord* boundary = NULL);

  // If "p" is in the space, returns the address of the start of the

  // "block" that contains "p".  We say "block" instead of "object" since

  // some heaps may not pack objects densely; a chunk may either be an

  // object or a non-object.  If "p" is not in the space, return NULL.

  virtual HeapWord* block_start(const void* p) const = 0;

  // Requires "addr" to be the start of a chunk, and returns its size.

  // "addr + size" is required to be the start of a new chunk, or the end

  // of the active area of the heap.

  virtual size_t block_size(const HeapWord* addr) const = 0;

  // Requires "addr" to be the start of a block, and returns "TRUE" iff

  // the block is an object.

  virtual bool block_is_obj(const HeapWord* addr) const = 0;

  // Requires "addr" to be the start of a block, and returns "TRUE" iff

  // the block is an object and the object is alive.

  virtual bool obj_is_alive(const HeapWord* addr) const;

  // Allocation (return NULL if full).  Assumes the caller has established

  // mutually exclusive access to the space.

  virtual HeapWord* allocate(size_t word_size) = 0;

  // Allocation (return NULL if full).  Enforces mutual exclusion internally.

  virtual HeapWord* par_allocate(size_t word_size) = 0;

  // Returns true if this object has been allocated since a

  // generation's "save_marks" call.

  virtual bool obj_allocated_since_save_marks(const oop obj) const = 0;

  // Mark-sweep-compact support: all spaces can update pointers to objects

  // moving as a part of compaction.

  virtual void adjust_pointers();

  // PrintHeapAtGC support

  virtual void print() const;

  virtual void print_on(outputStream* st) const;

  virtual void print_short() const;

  virtual void print_short_on(outputStream* st) const;

  // Accessor for parallel sequential tasks.

  SequentialSubTasksDone* par_seq_tasks() { return &_par_seq_tasks; }

  // IF "this" is a ContiguousSpace, return it, else return NULL.

  virtual ContiguousSpace* toContiguousSpace() {

    return NULL;

  }

  // Debugging

  virtual void verify(bool allow_dirty) const = 0;

};

// A MemRegionClosure (ResourceObj) whose "do_MemRegion" function applies an

// OopClosure to (the addresses of) all the ref-containing fields that could

// be modified by virtue of the given MemRegion being dirty. (Note that

// because of the imprecise nature of the write barrier, this may iterate

// over oops beyond the region.)

// This base type for dirty card to oop closures handles memory regions

// in non-contiguous spaces with no boundaries, and should be sub-classed

// to support other space types. See ContiguousDCTOC for a sub-class

// that works with ContiguousSpaces.

class DirtyCardToOopClosure: public MemRegionClosureRO {

protected:

  OopClosure* _cl;

  Space* _sp;

  CardTableModRefBS::PrecisionStyle _precision;

  HeapWord* _boundary;          // If non-NULL, process only non-NULL oops

                                // pointing below boundary.

  HeapWord* _min_done;          // ObjHeadPreciseArray precision requires

                                // a downwards traversal; this is the

                                // lowest location already done (or,

                                // alternatively, the lowest address that

                                // shouldn't be done again.  NULL means infinity.)

  NOT_PRODUCT(HeapWord* _last_bottom;)

  // Get the actual top of the area on which the closure will

  // operate, given where the top is assumed to be (the end of the

  // memory region passed to do_MemRegion) and where the object

  // at the top is assumed to start. For example, an object may

  // start at the top but actually extend past the assumed top,

  // in which case the top becomes the end of the object.

  virtual HeapWord* get_actual_top(HeapWord* top, HeapWord* top_obj);

  // Walk the given memory region from bottom to (actual) top

  // looking for objects and applying the oop closure (_cl) to

  // them. The base implementation of this treats the area as

  // blocks, where a block may or may not be an object. Sub-

  // classes should override this to provide more accurate

  // or possibly more efficient walking.

  virtual void walk_mem_region(MemRegion mr, HeapWord* bottom, HeapWord* top);

public:

  DirtyCardToOopClosure(Space* sp, OopClosure* cl,

                        CardTableModRefBS::PrecisionStyle precision,

                        HeapWord* boundary) :

    _sp(sp), _cl(cl), _precision(precision), _boundary(boundary),

    _min_done(NULL) {

    NOT_PRODUCT(_last_bottom = NULL;)

  }

  void do_MemRegion(MemRegion mr);

  void set_min_done(HeapWord* min_done) {

    _min_done = min_done;

  }

#ifndef PRODUCT

  void set_last_bottom(HeapWord* last_bottom) {

    _last_bottom = last_bottom;

  }

#endif

};

// A structure to represent a point at which objects are being copied

// during compaction.

class CompactPoint : public StackObj {

public:

  Generation* gen;

  CompactibleSpace* space;

  HeapWord* threshold;

  CompactPoint(Generation* _gen, CompactibleSpace* _space,

               HeapWord* _threshold) :

    gen(_gen), space(_space), threshold(_threshold) {}

};

// A space that supports compaction operations.  This is usually, but not

// necessarily, a space that is normally contiguous.  But, for example, a

// free-list-based space whose normal collection is a mark-sweep without

// compaction could still support compaction in full GC's.

class CompactibleSpace: public Space {

  friend class VMStructs;

  friend class CompactibleFreeListSpace;

  friend class CompactingPermGenGen;

  friend class CMSPermGenGen;

private:

  HeapWord* _compaction_top;

  CompactibleSpace* _next_compaction_space;

public:

  virtual void initialize(MemRegion mr, bool clear_space);

  // Used temporarily during a compaction phase to hold the value

  // top should have when compaction is complete.

  HeapWord* compaction_top() const { return _compaction_top;    }

  void set_compaction_top(HeapWord* value) {

    assert(value == NULL || (value >= bottom() && value <= end()),

      "should point inside space");

    _compaction_top = value;

  }

  // Perform operations on the space needed after a compaction

  // has been performed.

  virtual void reset_after_compaction() {}

  // Returns the next space (in the current generation) to be compacted in

  // the global compaction order.  Also is used to select the next

  // space into which to compact.

  virtual CompactibleSpace* next_compaction_space() const {

    return _next_compaction_space;

  }

  void set_next_compaction_space(CompactibleSpace* csp) {

    _next_compaction_space = csp;

  }

  // MarkSweep support phase2

  // Start the process of compaction of the current space: compute

  // post-compaction addresses, and insert forwarding pointers.  The fields

  // "cp->gen" and "cp->compaction_space" are the generation and space into

  // which we are currently compacting.  This call updates "cp" as necessary,

  // and leaves the "compaction_top" of the final value of

  // "cp->compaction_space" up-to-date.  Offset tables may be updated in

  // this phase as if the final copy had occurred; if so, "cp->threshold"

  // indicates when the next such action should be taken.

  virtual void prepare_for_compaction(CompactPoint* cp);

  // MarkSweep support phase3

  virtual void adjust_pointers();

  // MarkSweep support phase4

  virtual void compact();

  // The maximum percentage of objects that can be dead in the compacted

  // live part of a compacted space ("deadwood" support.)

  virtual int allowed_dead_ratio() const { return 0; };

  // Some contiguous spaces may maintain some data structures that should

  // be updated whenever an allocation crosses a boundary.  This function

  // returns the first such boundary.

  // (The default implementation returns the end of the space, so the

  // boundary is never crossed.)

  virtual HeapWord* initialize_threshold() { return end(); }

  // "q" is an object of the given "size" that should be forwarded;

  // "cp" names the generation ("gen") and containing "this" (which must

  // also equal "cp->space").  "compact_top" is where in "this" the

  // next object should be forwarded to.  If there is room in "this" for

  // the object, insert an appropriate forwarding pointer in "q".

  // If not, go to the next compaction space (there must

  // be one, since compaction must succeed -- we go to the first space of

  // the previous generation if necessary, updating "cp"), reset compact_top

  // and then forward.  In either case, returns the new value of "compact_top".

  // If the forwarding crosses "cp->threshold", invokes the "cross_threhold"

  // function of the then-current compaction space, and updates "cp->threshold

  // accordingly".

  virtual HeapWord* forward(oop q, size_t size, CompactPoint* cp,

                    HeapWord* compact_top);

  // Return a size with adjusments as required of the space.

  virtual size_t adjust_object_size_v(size_t size) const { return size; }

protected:

  // Used during compaction.

  HeapWord* _first_dead;

  HeapWord* _end_of_live;

  // Minimum size of a free block.

  virtual size_t minimum_free_block_size() const = 0;

  // This the function is invoked when an allocation of an object covering

  // "start" to "end occurs crosses the threshold; returns the next

  // threshold.  (The default implementation does nothing.)

  virtual HeapWord* cross_threshold(HeapWord* start, HeapWord* the_end) {

    return end();

  }

  // Requires "allowed_deadspace_words > 0", that "q" is the start of a

  // free block of the given "word_len", and that "q", were it an object,

  // would not move if forwared.  If the size allows, fill the free

  // block with an object, to prevent excessive compaction.  Returns "true"

  // iff the free region was made deadspace, and modifies

  // "allowed_deadspace_words" to reflect the number of available deadspace

  // words remaining after this operation.

  bool insert_deadspace(size_t& allowed_deadspace_words, HeapWord* q,

                        size_t word_len);

};

#define SCAN_AND_FORWARD(cp,scan_limit,block_is_obj,block_size) {            \

  /* Compute the new addresses for the live objects and store it in the mark \

   * Used by universe::mark_sweep_phase2()                                   \

   */                                                                        \

  HeapWord* compact_top; /* This is where we are currently compacting to. */ \

                                                                             \

  /* We're sure to be here before any objects are compacted into this        \

   * space, so this is a good time to initialize this:                       \

   */                                                                        \

  set_compaction_top(bottom());                                              \

                                                                             \

  if (cp->space == NULL) {                                                   \

    assert(cp->gen != NULL, "need a generation");                            \

    assert(cp->threshold == NULL, "just checking");                          \

    assert(cp->gen->first_compaction_space() == this, "just checking");      \

    cp->space = cp->gen->first_compaction_space();                           \

    compact_top = cp->space->bottom();                                       \

    cp->space->set_compaction_top(compact_top);                              \

    cp->threshold = cp->space->initialize_threshold();                       \

  } else {                                                                   \

    compact_top = cp->space->compaction_top();                               \

  }                                                                          \

                                                                             \

  /* We allow some amount of garbage towards the bottom of the space, so     \

   * we don't start compacting before there is a significant gain to be made.\

   * Occasionally, we want to ensure a full compaction, which is determined  \

   * by the MarkSweepAlwaysCompactCount parameter.                           \

   */                                                                        \

  int invocations = SharedHeap::heap()->perm_gen()->stat_record()->invocations;\

  bool skip_dead = ((invocations % MarkSweepAlwaysCompactCount) != 0);       \

                                                                             \

  size_t allowed_deadspace = 0;                                              \

  if (skip_dead) {                                                           \

    int ratio = allowed_dead_ratio();                                        \

    allowed_deadspace = (capacity() * ratio / 100) / HeapWordSize;           \

  }                                                                          \

                                                                             \

  HeapWord* q = bottom();                                                    \

  HeapWord* t = scan_limit();                                                \

                                                                             \

  HeapWord*  end_of_live= q;    /* One byte beyond the last byte of the last \

                                   live object. */                           \

  HeapWord*  first_dead = end();/* The first dead object. */                 \

  LiveRange* liveRange  = NULL; /* The current live range, recorded in the   \

                                   first header of preceding free area. */   \

  _first_dead = first_dead;                                                  \

                                                                             \

  const intx interval = PrefetchScanIntervalInBytes;                         \

                                                                             \

  while (q < t) {                                                            \

    assert(!block_is_obj(q) ||                                               \

           oop(q)->mark()->is_marked() || oop(q)->mark()->is_unlocked() ||   \

           oop(q)->mark()->has_bias_pattern(),                               \

           "these are the only valid states during a mark sweep");           \

    if (block_is_obj(q) && oop(q)->is_gc_marked()) {                         \

      /* prefetch beyond q */                                                \

      Prefetch::write(q, interval);                                          \

      /* size_t size = oop(q)->size();  changing this for cms for perm gen */\

      size_t size = block_size(q);                                           \

      compact_top = cp->space->forward(oop(q), size, cp, compact_top);       \

      q += size;                                                             \

      end_of_live = q;                                                       \

    } else {                                                                 \

      /* run over all the contiguous dead objects */                         \

      HeapWord* end = q;                                                     \

      do {                                                                   \

        /* prefetch beyond end */                                            \

        Prefetch::write(end, interval);                                      \

        end += block_size(end);                                              \

      } while (end < t && (!block_is_obj(end) || !oop(end)->is_gc_marked()));\

                                                                             \

      /* see if we might want to pretend this object is alive so that        \

       * we don't have to compact quite as often.                            \

       */                                                                    \

      if (allowed_deadspace > 0 && q == compact_top) {                       \

        size_t sz = pointer_delta(end, q);                                   \