// FIX ME FIX ME FIX ME FIX ME!!!!!!!!!
// The object forwarding code is duplicated. Factor this out!!!!!
//
// This method "precompacts" objects inside its space to dest. It places forwarding
// pointers into markOops for use by adjust_pointers. If "dest" should overflow, we
// finish by compacting into our own space.

void PSMarkSweepDecorator::precompact() {

  {- -------------------------------------------
  (1) 処理対象の領域(の中で実際に使用されている範囲)について, 
      その先頭(bottom)から最後(top)までを順に辿り, 
      markされている全てのオブジェクトに対して
      指定されたコンパクト先にコンパクションした際のアドレスを
      forwarding pointer として埋め込んでいく.

      (なお, 死んでいるオブジェクトには, 次の live object のアドレスを埋め込むことで
       phase3/phase4の際に連続したdead領域を一気にスキップできるようにしている.
       See: LiveRange)

      (なお, 新しいアドレスを実際に計算しているのは oopDesc::forward_to() メソッド)
      ---------------------------------------- -}

  {- -------------------------------------------
  (1) #TODO
      ---------------------------------------- -}

      // Reset our own compact top.
      set_compaction_top(space()->bottom());

  {- -------------------------------------------
  (1) 毎回全部コンパクションしていると遅いので, 普段は完全なコンパクションはしない.
      (より正確には, MarkSweepAlwaysCompactCount 回に 1 回しか完全なコンパクションは行わない)

      それ以外の場合(以下の skip_dead が true の場合)には, 
      領域の先頭にある程度の量のゴミが残っていてよいものとする.
      (この量を指定するのが, 以下の allowed_deadspace.
       allowed_deadspace は, コンパクション先の領域の大きさ(capacity)に, 
       PSMarkSweepDecorator::allowed_dead_ratio() の値を掛けて計算する.

       なお, PSMarkSweepDecorator::allowed_dead_ratio() は, 
       PSMarkSweepDecorator オブジェクトのコンストラクタや 
       PSMarkSweepDecorator::set_allowed_dead_ratio() で指定される値.
       See: MarkSweepDeadRatio, PermMarkSweepDeadRatio)
      ---------------------------------------- -}

      /* 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. This is a significant
       * performance improvement!
       */
      bool skip_dead = ((PSMarkSweep::total_invocations() % MarkSweepAlwaysCompactCount) != 0);

      size_t allowed_deadspace = 0;
      if (skip_dead) {
        const size_t ratio = allowed_dead_ratio();
        allowed_deadspace = space()->capacity_in_words() * ratio / 100;
      }

  {- -------------------------------------------
  (1) (変数宣言など)
      (q は現在処理しているオブジェクトを指すポインタ.
       t は処理範囲の終端を示すポインタ.)
      ---------------------------------------- -}

      // Fetch the current destination decorator
      PSMarkSweepDecorator* dest = destination_decorator();
      ObjectStartArray* start_array = dest->start_array();

      HeapWord* compact_top = dest->compaction_top();
      HeapWord* compact_end = dest->space()->end();

      HeapWord* q = space()->bottom();
      HeapWord* t = space()->top();

      HeapWord*  end_of_live= q;    /* One byte beyond the last byte of the last
                                       live object. */
      HeapWord*  first_dead = space()->end(); /* The first dead object. */
      LiveRange* liveRange  = NULL; /* The current live range, recorded in the
                                       first header of preceding free area. */

  {- -------------------------------------------
  (1) first_dead の情報は phase3 や phase4 でも使うため, _first_dead フィールドに記録しておく.
      (下の方でもう一回やっているような気もするが... #TODO)
      ---------------------------------------- -}

      _first_dead = first_dead;

  {- -------------------------------------------
  (1) (変数宣言など)
      ---------------------------------------- -}

      const intx interval = PrefetchScanIntervalInBytes;

  {- -------------------------------------------
  (1) 処理範囲の終端(t)に到達するまで, 次の while ループを繰り返して, 処理を行っていく.
      このループ内では以下のような処理を行う.

      * 処理対象の箇所(q)のオブジェクトが生きている場合 (= is_gc_marked() が true の場合):
        oopDesc::forward_to() で, そのオブジェクトにコンパクション先を指す forwarding pointer を埋める.
        その後, そのオブジェクトの大きさ分だけポインタ(q)を前に進める.
        (これにより, ループの次の週では, 次のオブジェクトに対する処理が始まる)

        (なお, 移動先が現在と同じアドレスの場合(= つまり, 移動しない場合)には, 
         そのオブジェクトの mark フィールドを初期状態の値にリセットするだけにしている.
         この情報は後で使用する.
         See: PSMarkSweepDecorator::adjust_pointers())

        (また, コンパクション先の領域に空き容量が足りない場合には, 
         コンパクション先を別の領域に切り替える処理も行っている)

      * dead オブジェクトに到達した場合 (= is_gc_marked() が false の場合):
        ゴミの量が allowed_deadspace に達するまでは, 
        たとえ死んでいても生きているオブジェクトと同様に扱う.
        (この場合, 上の生きている場合の処理とほぼ同じ)

        allowed_deadspace に達した後は,
        適切な LiveRange オブジェクトをその場に埋めた後, 
        次の live オブジェクトの位置までポインタ(q)を進める, という処理を行う.
        (これにより, dead オブジェクトばかりが続く領域は一気にスキップし, 
         ループの次の週では次の live オブジェクトに対する処理が始まる)

      (なお高速化のため, Prefetch::write() で 
       PrefetchScanIntervalInBytes バイトずつ
       メモリをプリフェッチしながら行う)
      ---------------------------------------- -}

      while (q < t) {

    {- -------------------------------------------
  (1.1) (assert)
        ---------------------------------------- -}

        assert(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");

    {- -------------------------------------------
  (1.1) 以下, 現在箇所のオブジェクトが生きている場合の処理:
        ---------------------------------------- -}

        if (oop(q)->is_gc_marked()) {

      {- -------------------------------------------
  (1.1.1) 高速化のためにプリフェッチしておく.
          ---------------------------------------- -}

          /* prefetch beyond q */
          Prefetch::write(q, interval);

      {- -------------------------------------------
  (1.1.1) (変数宣言など)
          ---------------------------------------- -}

          size_t size = oop(q)->size();

          size_t compaction_max_size = pointer_delta(compact_end, compact_top);

      {- -------------------------------------------
  (1.1.1) もし, 処理対象のオブジェクトの方が
          コンパクション先の領域の空き容量より大きい場合 (= その領域には入りきらない場合), 
          PSMarkSweepDecorator::advance_destination_decorator() で
          コンパクション先の領域を切り替える.

          (なお, 以下の while ループは入りきる領域が見つかるまで繰り返される)
          ---------------------------------------- -}

          // This should only happen if a space in the young gen overflows the
          // old gen. If that should happen, we null out the start_array, because
          // the young spaces are not covered by one.
          while(size > compaction_max_size) {
            // First record the last compact_top
            dest->set_compaction_top(compact_top);

            // Advance to the next compaction decorator
            advance_destination_decorator();
            dest = destination_decorator();

            // Update compaction info
            start_array = dest->start_array();
            compact_top = dest->compaction_top();
            compact_end = dest->space()->end();
            assert(compact_top == dest->space()->bottom(), "Advanced to space already in use");
            assert(compact_end > compact_top, "Must always be space remaining");
            compaction_max_size =
              pointer_delta(compact_end, compact_top);
          }

      {- -------------------------------------------
  (1.1.1) oopDesc::forward_to() で, 現在箇所のオブジェクト(q)に
          コンパクション先のアドレス(compact_top)を forwarding pointer として埋め込む.

          (ただし, 移動先が現在と同じアドレスの場合(= つまり, 移動しない場合)には, 
           oopDesc::init_mark() で, mark フィールドを初期状態の値にリセットするだけにしている.
           この情報は後で使用する.
           See: PSMarkSweepDecorator::adjust_pointers())
          ---------------------------------------- -}

          // store the forwarding pointer into the mark word
          if (q != compact_top) {
            oop(q)->forward_to(oop(compact_top));
            assert(oop(q)->is_gc_marked(), "encoding the pointer should preserve the mark");
          } else {
            // if the object isn't moving we can just set the mark to the default
            // mark and handle it specially later on.
            oop(q)->init_mark();
            assert(oop(q)->forwardee() == NULL, "should be forwarded to NULL");
          }

      {- -------------------------------------------
  (1.1.1) コンパクション先の offset array (start array) の値を更新しておく.
          ---------------------------------------- -}

          // Update object start array
          if (start_array) {
            start_array->allocate_block(compact_top);
          }

      {- -------------------------------------------
  (1.1.1) (verify)
          ---------------------------------------- -}

          VALIDATE_MARK_SWEEP_ONLY(MarkSweep::register_live_oop(oop(q), size));

      {- -------------------------------------------
  (1.1.1) 現在箇所を示すポインタ(q)やコンパクション先のアドレス(compact_top)を, 
          処理したオブジェクトの大きさ分だけ進める.
          (ついでに, end_of_live 変数の値も q に変更している)
          ---------------------------------------- -}

          compact_top += size;
          assert(compact_top <= dest->space()->end(),
            "Exceeding space in destination");

          q += size;
          end_of_live = q;

    {- -------------------------------------------
  (1.1) 以下, 現在箇所のオブジェクトが死んでいる場合の処理:
        ---------------------------------------- -}

        } else {

      {- -------------------------------------------
  (1.1.1) 次の live オブジェクトの位置を探す
          (以下の end に次の live オブジェクトの先頭アドレスが入る)
          ---------------------------------------- -}

          /* run over all the contiguous dead objects */
          HeapWord* end = q;
          do {
            /* prefetch beyond end */
            Prefetch::write(end, interval);
            end += oop(end)->size();
          } while (end < t && (!oop(end)->is_gc_marked()));

      {- -------------------------------------------
  (1.1.1) もし, ゴミの量が allowed_deadspace 量まで達していない場合には, 
          以下の if ブロック内の処理を行う.

          この場合には, 実際にはゴミオブジェクトであるが, live なオブジェクトとして扱う.
          (より正確には, 現在箇所(q)から次の live オブジェクト位置(end)までを
           1つの live オブジェクトが占めていると考え, 
           それに対して forwarding pointer を埋め込む, という処理を行う)

          この場合, if ブロックの最後に continue があるため, 
          if 以降の文は実行することなく, このままループの次の周へと進む.

          (allowed_deadspace 量まで達したかどうかは
           PSMarkSweepDecorator::insert_deadspace() で判定する.

           PSMarkSweepDecorator::insert_deadspace() は, 
           ゴミの量が allowed_deadspace 量に達するまでは
           コンパクション先に指定されたゴミオブジェクト領域と同サイズのダミーオブジェクトを生成して, true を返す.
           ゴミの量が allowed_deadspace 量に達して以降は, 単に false を返すだけ.

           なお, 正確には PSMarkSweepDecorator::insert_deadspace() は引数が参照渡しになっているため, 
           呼び出す度に allowed_deadspace の値が減少していく.
           ゴミの量が当初の allowed_deadspace 量に達した時点で, allowed_deadspace の値は 0 になる)
          ---------------------------------------- -}

          /* 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);
            if (insert_deadspace(allowed_deadspace, q, sz)) {
              size_t compaction_max_size = pointer_delta(compact_end, compact_top);

              // This should only happen if a space in the young gen overflows the
              // old gen. If that should happen, we null out the start_array, because
              // the young spaces are not covered by one.
              while (sz > compaction_max_size) {
                // First record the last compact_top
                dest->set_compaction_top(compact_top);

                // Advance to the next compaction decorator
                advance_destination_decorator();
                dest = destination_decorator();

                // Update compaction info
                start_array = dest->start_array();
                compact_top = dest->compaction_top();
                compact_end = dest->space()->end();
                assert(compact_top == dest->space()->bottom(), "Advanced to space already in use");
                assert(compact_end > compact_top, "Must always be space remaining");
                compaction_max_size =
                  pointer_delta(compact_end, compact_top);
              }

              // store the forwarding pointer into the mark word
              if (q != compact_top) {
                oop(q)->forward_to(oop(compact_top));
                assert(oop(q)->is_gc_marked(), "encoding the pointer should preserve the mark");
              } else {
                // if the object isn't moving we can just set the mark to the default
                // mark and handle it specially later on.
                oop(q)->init_mark();
                assert(oop(q)->forwardee() == NULL, "should be forwarded to NULL");
              }

              // Update object start array
              if (start_array) {
                start_array->allocate_block(compact_top);
              }

              VALIDATE_MARK_SWEEP_ONLY(MarkSweep::register_live_oop(oop(q), sz));
              compact_top += sz;
              assert(compact_top <= dest->space()->end(),
                "Exceeding space in destination");

              q = end;
              end_of_live = end;
              continue;
            }
          }

      {- -------------------------------------------
  (1.1.1) 一つ前の LiveRange の終端を, 今回見つけた dead 領域の先頭とする.
          ---------------------------------------- -}

          /* for the previous LiveRange, record the end of the live objects. */
          if (liveRange) {
            liveRange->set_end(q);
          }

      {- -------------------------------------------
  (1.1.1) 今回見つけた dead 領域の先頭に, 新しい LiveRange オブジェクトを作って埋め込んでおく.
          (この段階では, LiveRange の終端は適当な値にしておく (とりあえず先頭と同じアドレスにしている))
          ---------------------------------------- -}

          /* record the current LiveRange object.
           * liveRange->start() is overlaid on the mark word.
           */
          liveRange = (LiveRange*)q;
          liveRange->set_start(end);
          liveRange->set_end(end);

      {- -------------------------------------------
  (1.1.1) もしこれが最初の dead オブジェクトであれば, first_dead 変数の値を変更しておく.
          ---------------------------------------- -}

          /* see if this is the first dead region. */
          if (q < first_dead) {
            first_dead = q;
          }

      {- -------------------------------------------
  (1.1.1) q を次の live オブジェクト(end)に設定する
          (これにより, この後の dead オブジェクトが続いている領域については処理はスキップされる)
          ---------------------------------------- -}

          /* move on to the next object */
          q = end;
        }
      }

  {- -------------------------------------------
  (1) (assert)
      ---------------------------------------- -}

      assert(q == t, "just checking");

  {- -------------------------------------------
  (1) 最後の LiveRange の終端を現在箇所(q)に設定する.
      ---------------------------------------- -}

      if (liveRange != NULL) {
        liveRange->set_end(q);
      }

  {- -------------------------------------------
  (1) end_of_live や first_dead の情報は phase3 や phase4 でも使うため, 
      _end_of_live フィールドおよび _first_dead フィールドに記録しておく.
      ---------------------------------------- -}

      _end_of_live = end_of_live;
      if (end_of_live < first_dead) {
        first_dead = end_of_live;
      }
      _first_dead = first_dead;

  {- -------------------------------------------
  (1) PSMarkSweepDecorator::set_compaction_top() を呼んで, 
      コンパクション先の領域について, コンパクション先アドレスの情報を更新しておく. 
      ---------------------------------------- -}

      // Update compaction top
      dest->set_compaction_top(compact_top);
    }