Home | History | Annotate | Download | only in accounting 
      1 /*
      2  * Copyright (C) 2011 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #ifndef ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_INL_H_
     18 #define ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_INL_H_
     19 
     20 #include "card_table.h"
     21 
     22 #include <android-base/logging.h>
     23 
     24 #include "base/atomic.h"
     25 #include "base/bit_utils.h"
     26 #include "mem_map.h"
     27 #include "space_bitmap.h"
     28 
     29 namespace art {
     30 namespace gc {
     31 namespace accounting {
     32 
     33 static inline bool byte_cas(uint8_t old_value, uint8_t new_value, uint8_t* address) {
     34 #if defined(__i386__) || defined(__x86_64__)
     35   Atomic<uint8_t>* byte_atomic = reinterpret_cast<Atomic<uint8_t>*>(address);
     36   return byte_atomic->CompareAndSetWeakRelaxed(old_value, new_value);
     37 #else
     38   // Little endian means most significant byte is on the left.
     39   const size_t shift_in_bytes = reinterpret_cast<uintptr_t>(address) % sizeof(uintptr_t);
     40   // Align the address down.
     41   address -= shift_in_bytes;
     42   const size_t shift_in_bits = shift_in_bytes * kBitsPerByte;
     43   Atomic<uintptr_t>* word_atomic = reinterpret_cast<Atomic<uintptr_t>*>(address);
     44 
     45   // Word with the byte we are trying to cas cleared.
     46   const uintptr_t cur_word = word_atomic->LoadRelaxed() &
     47       ~(static_cast<uintptr_t>(0xFF) << shift_in_bits);
     48   const uintptr_t old_word = cur_word | (static_cast<uintptr_t>(old_value) << shift_in_bits);
     49   const uintptr_t new_word = cur_word | (static_cast<uintptr_t>(new_value) << shift_in_bits);
     50   return word_atomic->CompareAndSetWeakRelaxed(old_word, new_word);
     51 #endif
     52 }
     53 
     54 template <bool kClearCard, typename Visitor>
     55 inline size_t CardTable::Scan(ContinuousSpaceBitmap* bitmap,
     56                               uint8_t* const scan_begin,
     57                               uint8_t* const scan_end,
     58                               const Visitor& visitor,
     59                               const uint8_t minimum_age) {
     60   DCHECK_GE(scan_begin, reinterpret_cast<uint8_t*>(bitmap->HeapBegin()));
     61   // scan_end is the byte after the last byte we scan.
     62   DCHECK_LE(scan_end, reinterpret_cast<uint8_t*>(bitmap->HeapLimit()));
     63   uint8_t* const card_begin = CardFromAddr(scan_begin);
     64   uint8_t* const card_end = CardFromAddr(AlignUp(scan_end, kCardSize));
     65   uint8_t* card_cur = card_begin;
     66   CheckCardValid(card_cur);
     67   CheckCardValid(card_end);
     68   size_t cards_scanned = 0;
     69 
     70   // Handle any unaligned cards at the start.
     71   while (!IsAligned<sizeof(intptr_t)>(card_cur) && card_cur < card_end) {
     72     if (*card_cur >= minimum_age) {
     73       uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(card_cur));
     74       bitmap->VisitMarkedRange(start, start + kCardSize, visitor);
     75       ++cards_scanned;
     76     }
     77     ++card_cur;
     78   }
     79 
     80   uint8_t* aligned_end = card_end -
     81       (reinterpret_cast<uintptr_t>(card_end) & (sizeof(uintptr_t) - 1));
     82 
     83   uintptr_t* word_end = reinterpret_cast<uintptr_t*>(aligned_end);
     84   for (uintptr_t* word_cur = reinterpret_cast<uintptr_t*>(card_cur); word_cur < word_end;
     85       ++word_cur) {
     86     while (LIKELY(*word_cur == 0)) {
     87       ++word_cur;
     88       if (UNLIKELY(word_cur >= word_end)) {
     89         goto exit_for;
     90       }
     91     }
     92 
     93     // Find the first dirty card.
     94     uintptr_t start_word = *word_cur;
     95     uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(reinterpret_cast<uint8_t*>(word_cur)));
     96     // TODO: Investigate if processing continuous runs of dirty cards with a single bitmap visit is
     97     // more efficient.
     98     for (size_t i = 0; i < sizeof(uintptr_t); ++i) {
     99       if (static_cast<uint8_t>(start_word) >= minimum_age) {
    100         auto* card = reinterpret_cast<uint8_t*>(word_cur) + i;
    101         DCHECK(*card == static_cast<uint8_t>(start_word) || *card == kCardDirty)
    102             << "card " << static_cast<size_t>(*card) << " intptr_t " << (start_word & 0xFF);
    103         bitmap->VisitMarkedRange(start, start + kCardSize, visitor);
    104         ++cards_scanned;
    105       }
    106       start_word >>= 8;
    107       start += kCardSize;
    108     }
    109   }
    110   exit_for:
    111 
    112   // Handle any unaligned cards at the end.
    113   card_cur = reinterpret_cast<uint8_t*>(word_end);
    114   while (card_cur < card_end) {
    115     if (*card_cur >= minimum_age) {
    116       uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(card_cur));
    117       bitmap->VisitMarkedRange(start, start + kCardSize, visitor);
    118       ++cards_scanned;
    119     }
    120     ++card_cur;
    121   }
    122 
    123   if (kClearCard) {
    124     ClearCardRange(scan_begin, scan_end);
    125   }
    126 
    127   return cards_scanned;
    128 }
    129 
    130 /*
    131  * Visitor is expected to take in a card and return the new value. When a value is modified, the
    132  * modify visitor is called.
    133  * visitor: The visitor which modifies the cards. Returns the new value for a card given an old
    134  * value.
    135  * modified: Whenever the visitor modifies a card, this visitor is called on the card. Enables
    136  * us to know which cards got cleared.
    137  */
    138 template <typename Visitor, typename ModifiedVisitor>
    139 inline void CardTable::ModifyCardsAtomic(uint8_t* scan_begin,
    140                                          uint8_t* scan_end,
    141                                          const Visitor& visitor,
    142                                          const ModifiedVisitor& modified) {
    143   uint8_t* card_cur = CardFromAddr(scan_begin);
    144   uint8_t* card_end = CardFromAddr(AlignUp(scan_end, kCardSize));
    145   CheckCardValid(card_cur);
    146   CheckCardValid(card_end);
    147 
    148   // Handle any unaligned cards at the start.
    149   while (!IsAligned<sizeof(intptr_t)>(card_cur) && card_cur < card_end) {
    150     uint8_t expected, new_value;
    151     do {
    152       expected = *card_cur;
    153       new_value = visitor(expected);
    154     } while (expected != new_value && UNLIKELY(!byte_cas(expected, new_value, card_cur)));
    155     if (expected != new_value) {
    156       modified(card_cur, expected, new_value);
    157     }
    158     ++card_cur;
    159   }
    160 
    161   // Handle unaligned cards at the end.
    162   while (!IsAligned<sizeof(intptr_t)>(card_end) && card_end > card_cur) {
    163     --card_end;
    164     uint8_t expected, new_value;
    165     do {
    166       expected = *card_end;
    167       new_value = visitor(expected);
    168     } while (expected != new_value && UNLIKELY(!byte_cas(expected, new_value, card_end)));
    169     if (expected != new_value) {
    170       modified(card_end, expected, new_value);
    171     }
    172   }
    173 
    174   // Now we have the words, we can process words in parallel.
    175   uintptr_t* word_cur = reinterpret_cast<uintptr_t*>(card_cur);
    176   uintptr_t* word_end = reinterpret_cast<uintptr_t*>(card_end);
    177   // TODO: This is not big endian safe.
    178   union {
    179     uintptr_t expected_word;
    180     uint8_t expected_bytes[sizeof(uintptr_t)];
    181   };
    182   union {
    183     uintptr_t new_word;
    184     uint8_t new_bytes[sizeof(uintptr_t)];
    185   };
    186 
    187   // TODO: Parallelize.
    188   while (word_cur < word_end) {
    189     while (true) {
    190       expected_word = *word_cur;
    191       if (LIKELY(expected_word == 0)) {
    192         break;
    193       }
    194       for (size_t i = 0; i < sizeof(uintptr_t); ++i) {
    195         new_bytes[i] = visitor(expected_bytes[i]);
    196       }
    197       Atomic<uintptr_t>* atomic_word = reinterpret_cast<Atomic<uintptr_t>*>(word_cur);
    198       if (LIKELY(atomic_word->CompareAndSetWeakRelaxed(expected_word, new_word))) {
    199         for (size_t i = 0; i < sizeof(uintptr_t); ++i) {
    200           const uint8_t expected_byte = expected_bytes[i];
    201           const uint8_t new_byte = new_bytes[i];
    202           if (expected_byte != new_byte) {
    203             modified(reinterpret_cast<uint8_t*>(word_cur) + i, expected_byte, new_byte);
    204           }
    205         }
    206         break;
    207       }
    208     }
    209     ++word_cur;
    210   }
    211 }
    212 
    213 inline void* CardTable::AddrFromCard(const uint8_t *card_addr) const {
    214   DCHECK(IsValidCard(card_addr))
    215     << " card_addr: " << reinterpret_cast<const void*>(card_addr)
    216     << " begin: " << reinterpret_cast<void*>(mem_map_->Begin() + offset_)
    217     << " end: " << reinterpret_cast<void*>(mem_map_->End());
    218   uintptr_t offset = card_addr - biased_begin_;
    219   return reinterpret_cast<void*>(offset << kCardShift);
    220 }
    221 
    222 inline uint8_t* CardTable::CardFromAddr(const void *addr) const {
    223   uint8_t *card_addr = biased_begin_ + (reinterpret_cast<uintptr_t>(addr) >> kCardShift);
    224   // Sanity check the caller was asking for address covered by the card table
    225   DCHECK(IsValidCard(card_addr)) << "addr: " << addr
    226       << " card_addr: " << reinterpret_cast<void*>(card_addr);
    227   return card_addr;
    228 }
    229 
    230 inline bool CardTable::IsValidCard(const uint8_t* card_addr) const {
    231   uint8_t* begin = mem_map_->Begin() + offset_;
    232   uint8_t* end = mem_map_->End();
    233   return card_addr >= begin && card_addr < end;
    234 }
    235 
    236 inline void CardTable::CheckCardValid(uint8_t* card) const {
    237   DCHECK(IsValidCard(card))
    238       << " card_addr: " << reinterpret_cast<const void*>(card)
    239       << " begin: " << reinterpret_cast<void*>(mem_map_->Begin() + offset_)
    240       << " end: " << reinterpret_cast<void*>(mem_map_->End());
    241 }
    242 
    243 }  // namespace accounting
    244 }  // namespace gc
    245 }  // namespace art
    246 
    247 #endif  // ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_INL_H_
    248