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 "atomic.h"
     21 #include "base/logging.h"
     22 #include "card_table.h"
     23 #include "space_bitmap.h"
     24 #include "utils.h"
     25 
     26 namespace art {
     27 namespace gc {
     28 namespace accounting {
     29 
     30 static inline bool byte_cas(byte old_value, byte new_value, byte* address) {
     31 #if defined(__i386__) || defined(__x86_64__)
     32   Atomic<byte>* byte_atomic = reinterpret_cast<Atomic<byte>*>(address);
     33   return byte_atomic->CompareExchangeWeakRelaxed(old_value, new_value);
     34 #else
     35   // Little endian means most significant byte is on the left.
     36   const size_t shift_in_bytes = reinterpret_cast<uintptr_t>(address) % sizeof(uintptr_t);
     37   // Align the address down.
     38   address -= shift_in_bytes;
     39   const size_t shift_in_bits = shift_in_bytes * kBitsPerByte;
     40   Atomic<uintptr_t>* word_atomic = reinterpret_cast<Atomic<uintptr_t>*>(address);
     41 
     42   // Word with the byte we are trying to cas cleared.
     43   const uintptr_t cur_word = word_atomic->LoadRelaxed() &
     44       ~(static_cast<uintptr_t>(0xFF) << shift_in_bits);
     45   const uintptr_t old_word = cur_word | (static_cast<uintptr_t>(old_value) << shift_in_bits);
     46   const uintptr_t new_word = cur_word | (static_cast<uintptr_t>(new_value) << shift_in_bits);
     47   return word_atomic->CompareExchangeWeakRelaxed(old_word, new_word);
     48 #endif
     49 }
     50 
     51 template <typename Visitor>
     52 inline size_t CardTable::Scan(ContinuousSpaceBitmap* bitmap, byte* scan_begin, byte* scan_end,
     53                               const Visitor& visitor, const byte minimum_age) const {
     54   DCHECK_GE(scan_begin, reinterpret_cast<byte*>(bitmap->HeapBegin()));
     55   // scan_end is the byte after the last byte we scan.
     56   DCHECK_LE(scan_end, reinterpret_cast<byte*>(bitmap->HeapLimit()));
     57   byte* card_cur = CardFromAddr(scan_begin);
     58   byte* card_end = CardFromAddr(AlignUp(scan_end, kCardSize));
     59   CheckCardValid(card_cur);
     60   CheckCardValid(card_end);
     61   size_t cards_scanned = 0;
     62 
     63   // Handle any unaligned cards at the start.
     64   while (!IsAligned<sizeof(word)>(card_cur) && card_cur < card_end) {
     65     if (*card_cur >= minimum_age) {
     66       uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(card_cur));
     67       bitmap->VisitMarkedRange(start, start + kCardSize, visitor);
     68       ++cards_scanned;
     69     }
     70     ++card_cur;
     71   }
     72 
     73   byte* aligned_end = card_end -
     74       (reinterpret_cast<uintptr_t>(card_end) & (sizeof(uintptr_t) - 1));
     75 
     76   uintptr_t* word_end = reinterpret_cast<uintptr_t*>(aligned_end);
     77   for (uintptr_t* word_cur = reinterpret_cast<uintptr_t*>(card_cur); word_cur < word_end;
     78       ++word_cur) {
     79     while (LIKELY(*word_cur == 0)) {
     80       ++word_cur;
     81       if (UNLIKELY(word_cur >= word_end)) {
     82         goto exit_for;
     83       }
     84     }
     85 
     86     // Find the first dirty card.
     87     uintptr_t start_word = *word_cur;
     88     uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(reinterpret_cast<byte*>(word_cur)));
     89     // TODO: Investigate if processing continuous runs of dirty cards with a single bitmap visit is
     90     // more efficient.
     91     for (size_t i = 0; i < sizeof(uintptr_t); ++i) {
     92       if (static_cast<byte>(start_word) >= minimum_age) {
     93         auto* card = reinterpret_cast<byte*>(word_cur) + i;
     94         DCHECK(*card == static_cast<byte>(start_word) || *card == kCardDirty)
     95             << "card " << static_cast<size_t>(*card) << " word " << (start_word & 0xFF);
     96         bitmap->VisitMarkedRange(start, start + kCardSize, visitor);
     97         ++cards_scanned;
     98       }
     99       start_word >>= 8;
    100       start += kCardSize;
    101     }
    102   }
    103   exit_for:
    104 
    105   // Handle any unaligned cards at the end.
    106   card_cur = reinterpret_cast<byte*>(word_end);
    107   while (card_cur < card_end) {
    108     if (*card_cur >= minimum_age) {
    109       uintptr_t start = reinterpret_cast<uintptr_t>(AddrFromCard(card_cur));
    110       bitmap->VisitMarkedRange(start, start + kCardSize, visitor);
    111       ++cards_scanned;
    112     }
    113     ++card_cur;
    114   }
    115 
    116   return cards_scanned;
    117 }
    118 
    119 /*
    120  * Visitor is expected to take in a card and return the new value. When a value is modified, the
    121  * modify visitor is called.
    122  * visitor: The visitor which modifies the cards. Returns the new value for a card given an old
    123  * value.
    124  * modified: Whenever the visitor modifies a card, this visitor is called on the card. Enables
    125  * us to know which cards got cleared.
    126  */
    127 template <typename Visitor, typename ModifiedVisitor>
    128 inline void CardTable::ModifyCardsAtomic(byte* scan_begin, byte* scan_end, const Visitor& visitor,
    129                                          const ModifiedVisitor& modified) {
    130   byte* card_cur = CardFromAddr(scan_begin);
    131   byte* card_end = CardFromAddr(AlignUp(scan_end, kCardSize));
    132   CheckCardValid(card_cur);
    133   CheckCardValid(card_end);
    134 
    135   // Handle any unaligned cards at the start.
    136   while (!IsAligned<sizeof(word)>(card_cur) && card_cur < card_end) {
    137     byte expected, new_value;
    138     do {
    139       expected = *card_cur;
    140       new_value = visitor(expected);
    141     } while (expected != new_value && UNLIKELY(!byte_cas(expected, new_value, card_cur)));
    142     if (expected != new_value) {
    143       modified(card_cur, expected, new_value);
    144     }
    145     ++card_cur;
    146   }
    147 
    148   // Handle unaligned cards at the end.
    149   while (!IsAligned<sizeof(word)>(card_end) && card_end > card_cur) {
    150     --card_end;
    151     byte expected, new_value;
    152     do {
    153       expected = *card_end;
    154       new_value = visitor(expected);
    155     } while (expected != new_value && UNLIKELY(!byte_cas(expected, new_value, card_end)));
    156     if (expected != new_value) {
    157       modified(card_end, expected, new_value);
    158     }
    159   }
    160 
    161   // Now we have the words, we can process words in parallel.
    162   uintptr_t* word_cur = reinterpret_cast<uintptr_t*>(card_cur);
    163   uintptr_t* word_end = reinterpret_cast<uintptr_t*>(card_end);
    164   // TODO: This is not big endian safe.
    165   union {
    166     uintptr_t expected_word;
    167     uint8_t expected_bytes[sizeof(uintptr_t)];
    168   };
    169   union {
    170     uintptr_t new_word;
    171     uint8_t new_bytes[sizeof(uintptr_t)];
    172   };
    173 
    174   // TODO: Parallelize.
    175   while (word_cur < word_end) {
    176     while (true) {
    177       expected_word = *word_cur;
    178       if (LIKELY(expected_word == 0)) {
    179         break;
    180       }
    181       for (size_t i = 0; i < sizeof(uintptr_t); ++i) {
    182         new_bytes[i] = visitor(expected_bytes[i]);
    183       }
    184       Atomic<uintptr_t>* atomic_word = reinterpret_cast<Atomic<uintptr_t>*>(word_cur);
    185       if (LIKELY(atomic_word->CompareExchangeWeakRelaxed(expected_word, new_word))) {
    186         for (size_t i = 0; i < sizeof(uintptr_t); ++i) {
    187           const byte expected_byte = expected_bytes[i];
    188           const byte new_byte = new_bytes[i];
    189           if (expected_byte != new_byte) {
    190             modified(reinterpret_cast<byte*>(word_cur) + i, expected_byte, new_byte);
    191           }
    192         }
    193         break;
    194       }
    195     }
    196     ++word_cur;
    197   }
    198 }
    199 
    200 inline void* CardTable::AddrFromCard(const byte *card_addr) const {
    201   DCHECK(IsValidCard(card_addr))
    202     << " card_addr: " << reinterpret_cast<const void*>(card_addr)
    203     << " begin: " << reinterpret_cast<void*>(mem_map_->Begin() + offset_)
    204     << " end: " << reinterpret_cast<void*>(mem_map_->End());
    205   uintptr_t offset = card_addr - biased_begin_;
    206   return reinterpret_cast<void*>(offset << kCardShift);
    207 }
    208 
    209 inline byte* CardTable::CardFromAddr(const void *addr) const {
    210   byte *card_addr = biased_begin_ + (reinterpret_cast<uintptr_t>(addr) >> kCardShift);
    211   // Sanity check the caller was asking for address covered by the card table
    212   DCHECK(IsValidCard(card_addr)) << "addr: " << addr
    213       << " card_addr: " << reinterpret_cast<void*>(card_addr);
    214   return card_addr;
    215 }
    216 
    217 inline void CardTable::CheckCardValid(byte* card) const {
    218   DCHECK(IsValidCard(card))
    219       << " card_addr: " << reinterpret_cast<const void*>(card)
    220       << " begin: " << reinterpret_cast<void*>(mem_map_->Begin() + offset_)
    221       << " end: " << reinterpret_cast<void*>(mem_map_->End());
    222 }
    223 
    224 }  // namespace accounting
    225 }  // namespace gc
    226 }  // namespace art
    227 
    228 #endif  // ART_RUNTIME_GC_ACCOUNTING_CARD_TABLE_INL_H_
    229