runtime/gc/accounting/card_table-inl.h

/*
 * Copyright (C) 2011 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_INL_H_
#define ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_INL_H_

#include "atomic.h"
#include "base/bit_utils.h"
#include "base/logging.h"
#include "card_table.h"
#include "mem_map.h"
#include "space_bitmap.h"

namespace art {
namespace gc {
namespace accounting {

static inline bool byte_cas(uint8_t old_value, uint8_t new_value, uint8_t* address) {
#if defined(__i386__) || defined(__x86_64__)
  Atomic<uint8_t>* byte_atomic = reinterpret_cast<Atomic<uint8_t>*>(address);
  return byte_atomic->CompareExchangeWeakRelaxed(old_value, new_value);
#else
  // Little endian means most significant byte is on the left.
  const size_t shift_in_bytes = reinterpret_cast<uintptr_t>(address) % sizeof(uintptr_t);
  // Align the address down.
  address -= shift_in_bytes;
  const size_t shift_in_bits = shift_in_bytes * kBitsPerByte;
  Atomic<uintptr_t>* word_atomic = reinterpret_cast<Atomic<uintptr_t>*>(address);

  // Word with the byte we are trying to cas cleared.
  const uintptr_t cur_word = word_atomic->LoadRelaxed() &
      ~(static_cast<uintptr_t>(0xFF) << shift_in_bits);
  const uintptr_t old_word = cur_word | (static_cast<uintptr_t>(old_value) << shift_in_bits);
  const uintptr_t new_word = cur_word | (static_cast<uintptr_t>(new_value) << shift_in_bits);
  return word_atomic->CompareExchangeWeakRelaxed(old_word, new_word);
#endif
}

template <bool kClearCard, typename Visitor>
inline size_t CardTable::Scan(ContinuousSpaceBitmap* bitmap,
                              uint8_t* const scan_begin,
                              uint8_t* const scan_end,
                              const Visitor& visitor,
                              const uint8_t minimum_age) {
  DCHECK_GE(scan_begin, reinterpret_cast<uint8_t*>(bitmap->HeapBegin()));
  // scan_end is the byte after the last byte we scan.
  DCHECK_LE(scan_end, reinterpret_cast<uint8_t*>(bitmap->HeapLimit()));
  uint8_t* const card_begin = CardFromAddr(scan_begin);
  uint8_t* const card_end = CardFromAddr(AlignUp(scan_end, kCardSize));
  uint8_t* card_cur = card_begin;
  CheckCardValid(card_cur);
  CheckCardValid(card_end);
  size_t cards_scanned = 0;

  // Handle any unaligned cards at the start.
  while (!IsAligned<sizeof(intptr_t)>(card_cur) && card_cur < card_end) {
    if (*card_cur >= minimum_age) {
      uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(card_cur));
      bitmap->VisitMarkedRange(start, start + kCardSize, visitor);
      ++cards_scanned;
    }
    ++card_cur;
  }

  uint8_t* aligned_end = card_end -
      (reinterpret_cast<uintptr_t>(card_end) & (sizeof(uintptr_t) - 1));

  uintptr_t* word_end = reinterpret_cast<uintptr_t*>(aligned_end);
  for (uintptr_t* word_cur = reinterpret_cast<uintptr_t*>(card_cur); word_cur < word_end;
      ++word_cur) {
    while (LIKELY(*word_cur == 0)) {
      ++word_cur;
      if (UNLIKELY(word_cur >= word_end)) {
        goto exit_for;
      }
    }

    // Find the first dirty card.
    uintptr_t start_word = *word_cur;
    uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(reinterpret_cast<uint8_t*>(word_cur)));
    // TODO: Investigate if processing continuous runs of dirty cards with a single bitmap visit is
    // more efficient.
    for (size_t i = 0; i < sizeof(uintptr_t); ++i) {
      if (static_cast<uint8_t>(start_word) >= minimum_age) {
        auto* card = reinterpret_cast<uint8_t*>(word_cur) + i;
        DCHECK(*card == static_cast<uint8_t>(start_word) || *card == kCardDirty)
            << "card " << static_cast<size_t>(*card) << " intptr_t " << (start_word & 0xFF);
        bitmap->VisitMarkedRange(start, start + kCardSize, visitor);
        ++cards_scanned;
      }
      start_word >>= 8;
      start += kCardSize;
    }
  }
  exit_for:

  // Handle any unaligned cards at the end.
  card_cur = reinterpret_cast<uint8_t*>(word_end);
  while (card_cur < card_end) {
    if (*card_cur >= minimum_age) {
      uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(card_cur));
      bitmap->VisitMarkedRange(start, start + kCardSize, visitor);
      ++cards_scanned;
    }
    ++card_cur;
  }

  if (kClearCard) {
    ClearCardRange(scan_begin, scan_end);
  }

  return cards_scanned;
}

/*
 * Visitor is expected to take in a card and return the new value. When a value is modified, the
 * modify visitor is called.
 * visitor: The visitor which modifies the cards. Returns the new value for a card given an old
 * value.
 * modified: Whenever the visitor modifies a card, this visitor is called on the card. Enables
 * us to know which cards got cleared.
 */
template <typename Visitor, typename ModifiedVisitor>
inline void CardTable::ModifyCardsAtomic(uint8_t* scan_begin,
                                         uint8_t* scan_end,
                                         const Visitor& visitor,
                                         const ModifiedVisitor& modified) {
  uint8_t* card_cur = CardFromAddr(scan_begin);
  uint8_t* card_end = CardFromAddr(AlignUp(scan_end, kCardSize));
  CheckCardValid(card_cur);
  CheckCardValid(card_end);

  // Handle any unaligned cards at the start.
  while (!IsAligned<sizeof(intptr_t)>(card_cur) && card_cur < card_end) {
    uint8_t expected, new_value;
    do {
      expected = *card_cur;
      new_value = visitor(expected);
    } while (expected != new_value && UNLIKELY(!byte_cas(expected, new_value, card_cur)));
    if (expected != new_value) {
      modified(card_cur, expected, new_value);
    }
    ++card_cur;
  }

  // Handle unaligned cards at the end.
  while (!IsAligned<sizeof(intptr_t)>(card_end) && card_end > card_cur) {
    --card_end;
    uint8_t expected, new_value;
    do {
      expected = *card_end;
      new_value = visitor(expected);
    } while (expected != new_value && UNLIKELY(!byte_cas(expected, new_value, card_end)));
    if (expected != new_value) {
      modified(card_end, expected, new_value);
    }
  }

  // Now we have the words, we can process words in parallel.
  uintptr_t* word_cur = reinterpret_cast<uintptr_t*>(card_cur);
  uintptr_t* word_end = reinterpret_cast<uintptr_t*>(card_end);
  // TODO: This is not big endian safe.
  union {
    uintptr_t expected_word;
    uint8_t expected_bytes[sizeof(uintptr_t)];
  };
  union {
    uintptr_t new_word;
    uint8_t new_bytes[sizeof(uintptr_t)];
  };

  // TODO: Parallelize.
  while (word_cur < word_end) {
    while (true) {
      expected_word = *word_cur;
      if (LIKELY(expected_word == 0)) {
        break;
      }
      for (size_t i = 0; i < sizeof(uintptr_t); ++i) {
        new_bytes[i] = visitor(expected_bytes[i]);
      }
      Atomic<uintptr_t>* atomic_word = reinterpret_cast<Atomic<uintptr_t>*>(word_cur);
      if (LIKELY(atomic_word->CompareExchangeWeakRelaxed(expected_word, new_word))) {
        for (size_t i = 0; i < sizeof(uintptr_t); ++i) {
          const uint8_t expected_byte = expected_bytes[i];
          const uint8_t new_byte = new_bytes[i];
          if (expected_byte != new_byte) {
            modified(reinterpret_cast<uint8_t*>(word_cur) + i, expected_byte, new_byte);
          }
        }
        break;
      }
    }
    ++word_cur;
  }
}

inline void* CardTable::AddrFromCard(const uint8_t *card_addr) const {
  DCHECK(IsValidCard(card_addr))
    << " card_addr: " << reinterpret_cast<const void*>(card_addr)
    << " begin: " << reinterpret_cast<void*>(mem_map_->Begin() + offset_)
    << " end: " << reinterpret_cast<void*>(mem_map_->End());
  uintptr_t offset = card_addr - biased_begin_;
  return reinterpret_cast<void*>(offset << kCardShift);
}

inline uint8_t* CardTable::CardFromAddr(const void *addr) const {
  uint8_t *card_addr = biased_begin_ + (reinterpret_cast<uintptr_t>(addr) >> kCardShift);
  // Sanity check the caller was asking for address covered by the card table
  DCHECK(IsValidCard(card_addr)) << "addr: " << addr
      << " card_addr: " << reinterpret_cast<void*>(card_addr);
  return card_addr;
}

inline bool CardTable::IsValidCard(const uint8_t* card_addr) const {
  uint8_t* begin = mem_map_->Begin() + offset_;
  uint8_t* end = mem_map_->End();
  return card_addr >= begin && card_addr < end;
}

inline void CardTable::CheckCardValid(uint8_t* card) const {
  DCHECK(IsValidCard(card))
      << " card_addr: " << reinterpret_cast<const void*>(card)
      << " begin: " << reinterpret_cast<void*>(mem_map_->Begin() + offset_)
      << " end: " << reinterpret_cast<void*>(mem_map_->End());
}

}  // namespace accounting
}  // namespace gc
}  // namespace art

#endif  // ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_INL_H_