Home | History | Annotate | Download | only in accounting 
      1 /*
      2  * Copyright (C) 2008 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_SPACE_BITMAP_INL_H_
     18 #define ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_
     19 
     20 #include "space_bitmap.h"
     21 
     22 #include <memory>
     23 
     24 #include "atomic.h"
     25 #include "base/logging.h"
     26 #include "utils.h"
     27 
     28 namespace art {
     29 namespace gc {
     30 namespace accounting {
     31 
     32 template<size_t kAlignment>
     33 inline bool SpaceBitmap<kAlignment>::AtomicTestAndSet(const mirror::Object* obj) {
     34   uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
     35   DCHECK_GE(addr, heap_begin_);
     36   const uintptr_t offset = addr - heap_begin_;
     37   const size_t index = OffsetToIndex(offset);
     38   const uword mask = OffsetToMask(offset);
     39   Atomic<uword>* atomic_entry = reinterpret_cast<Atomic<uword>*>(&bitmap_begin_[index]);
     40   DCHECK_LT(index, bitmap_size_ / kWordSize) << " bitmap_size_ = " << bitmap_size_;
     41   uword old_word;
     42   do {
     43     old_word = atomic_entry->LoadRelaxed();
     44     // Fast path: The bit is already set.
     45     if ((old_word & mask) != 0) {
     46       DCHECK(Test(obj));
     47       return true;
     48     }
     49   } while (!atomic_entry->CompareExchangeWeakSequentiallyConsistent(old_word, old_word | mask));
     50   DCHECK(Test(obj));
     51   return false;
     52 }
     53 
     54 template<size_t kAlignment>
     55 inline bool SpaceBitmap<kAlignment>::Test(const mirror::Object* obj) const {
     56   uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
     57   DCHECK(HasAddress(obj)) << obj;
     58   DCHECK(bitmap_begin_ != NULL);
     59   DCHECK_GE(addr, heap_begin_);
     60   const uintptr_t offset = addr - heap_begin_;
     61   return (bitmap_begin_[OffsetToIndex(offset)] & OffsetToMask(offset)) != 0;
     62 }
     63 
     64 template<size_t kAlignment> template<typename Visitor>
     65 inline void SpaceBitmap<kAlignment>::VisitMarkedRange(uintptr_t visit_begin, uintptr_t visit_end,
     66                                                       const Visitor& visitor) const {
     67   DCHECK_LE(visit_begin, visit_end);
     68 #if 0
     69   for (uintptr_t i = visit_begin; i < visit_end; i += kAlignment) {
     70     mirror::Object* obj = reinterpret_cast<mirror::Object*>(i);
     71     if (Test(obj)) {
     72       visitor(obj);
     73     }
     74   }
     75 #else
     76   DCHECK_LE(heap_begin_, visit_begin);
     77   DCHECK_LE(visit_end, HeapLimit());
     78 
     79   const uintptr_t offset_start = visit_begin - heap_begin_;
     80   const uintptr_t offset_end = visit_end - heap_begin_;
     81 
     82   const uintptr_t index_start = OffsetToIndex(offset_start);
     83   const uintptr_t index_end = OffsetToIndex(offset_end);
     84 
     85   const size_t bit_start = (offset_start / kAlignment) % kBitsPerWord;
     86   const size_t bit_end = (offset_end / kAlignment) % kBitsPerWord;
     87 
     88   // Index(begin)  ...    Index(end)
     89   // [xxxxx???][........][????yyyy]
     90   //      ^                   ^
     91   //      |                   #---- Bit of visit_end
     92   //      #---- Bit of visit_begin
     93   //
     94 
     95   // Left edge.
     96   uword left_edge = bitmap_begin_[index_start];
     97   // Mark of lower bits that are not in range.
     98   left_edge &= ~((static_cast<uword>(1) << bit_start) - 1);
     99 
    100   // Right edge. Either unique, or left_edge.
    101   uword right_edge;
    102 
    103   if (index_start < index_end) {
    104     // Left edge != right edge.
    105 
    106     // Traverse left edge.
    107     if (left_edge != 0) {
    108       const uintptr_t ptr_base = IndexToOffset(index_start) + heap_begin_;
    109       do {
    110         const size_t shift = CTZ(left_edge);
    111         mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
    112         visitor(obj);
    113         left_edge ^= (static_cast<uword>(1)) << shift;
    114       } while (left_edge != 0);
    115     }
    116 
    117     // Traverse the middle, full part.
    118     for (size_t i = index_start + 1; i < index_end; ++i) {
    119       uword w = bitmap_begin_[i];
    120       if (w != 0) {
    121         const uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
    122         do {
    123           const size_t shift = CTZ(w);
    124           mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
    125           visitor(obj);
    126           w ^= (static_cast<uword>(1)) << shift;
    127         } while (w != 0);
    128       }
    129     }
    130 
    131     // Right edge is unique.
    132     // But maybe we don't have anything to do: visit_end starts in a new word...
    133     if (bit_end == 0) {
    134       // Do not read memory, as it could be after the end of the bitmap.
    135       right_edge = 0;
    136     } else {
    137       right_edge = bitmap_begin_[index_end];
    138     }
    139   } else {
    140     // Right edge = left edge.
    141     right_edge = left_edge;
    142   }
    143 
    144   // Right edge handling.
    145   right_edge &= ((static_cast<uword>(1) << bit_end) - 1);
    146   if (right_edge != 0) {
    147     const uintptr_t ptr_base = IndexToOffset(index_end) + heap_begin_;
    148     do {
    149       const size_t shift = CTZ(right_edge);
    150       mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
    151       visitor(obj);
    152       right_edge ^= (static_cast<uword>(1)) << shift;
    153     } while (right_edge != 0);
    154   }
    155 #endif
    156 }
    157 
    158 template<size_t kAlignment> template<bool kSetBit>
    159 inline bool SpaceBitmap<kAlignment>::Modify(const mirror::Object* obj) {
    160   uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
    161   DCHECK_GE(addr, heap_begin_);
    162   const uintptr_t offset = addr - heap_begin_;
    163   const size_t index = OffsetToIndex(offset);
    164   const uword mask = OffsetToMask(offset);
    165   DCHECK_LT(index, bitmap_size_ / kWordSize) << " bitmap_size_ = " << bitmap_size_;
    166   uword* address = &bitmap_begin_[index];
    167   uword old_word = *address;
    168   if (kSetBit) {
    169     *address = old_word | mask;
    170   } else {
    171     *address = old_word & ~mask;
    172   }
    173   DCHECK_EQ(Test(obj), kSetBit);
    174   return (old_word & mask) != 0;
    175 }
    176 
    177 template<size_t kAlignment>
    178 inline std::ostream& operator << (std::ostream& stream, const SpaceBitmap<kAlignment>& bitmap) {
    179   return stream
    180     << bitmap.GetName() << "["
    181     << "begin=" << reinterpret_cast<const void*>(bitmap.HeapBegin())
    182     << ",end=" << reinterpret_cast<const void*>(bitmap.HeapLimit())
    183     << "]";
    184 }
    185 
    186 }  // namespace accounting
    187 }  // namespace gc
    188 }  // namespace art
    189 
    190 #endif  // ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_
    191