Home | History | Annotate | Download | only in accounting 
      1 /*
      2  * Copyright (C) 2015 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_BITMAP_INL_H_
     18 #define ART_RUNTIME_GC_ACCOUNTING_BITMAP_INL_H_
     19 
     20 #include "bitmap.h"
     21 
     22 #include <memory>
     23 
     24 #include "atomic.h"
     25 #include "base/bit_utils.h"
     26 #include "base/logging.h"
     27 
     28 namespace art {
     29 namespace gc {
     30 namespace accounting {
     31 
     32 inline bool Bitmap::AtomicTestAndSetBit(uintptr_t bit_index) {
     33   CheckValidBitIndex(bit_index);
     34   const size_t word_index = BitIndexToWordIndex(bit_index);
     35   const uintptr_t word_mask = BitIndexToMask(bit_index);
     36   auto* atomic_entry = reinterpret_cast<Atomic<uintptr_t>*>(&bitmap_begin_[word_index]);
     37   uintptr_t old_word;
     38   do {
     39     old_word = atomic_entry->LoadRelaxed();
     40     // Fast path: The bit is already set.
     41     if ((old_word & word_mask) != 0) {
     42       DCHECK(TestBit(bit_index));
     43       return true;
     44     }
     45   } while (!atomic_entry->CompareExchangeWeakSequentiallyConsistent(old_word,
     46                                                                     old_word | word_mask));
     47   DCHECK(TestBit(bit_index));
     48   return false;
     49 }
     50 
     51 inline bool Bitmap::TestBit(uintptr_t bit_index) const {
     52   CheckValidBitIndex(bit_index);
     53   return (bitmap_begin_[BitIndexToWordIndex(bit_index)] & BitIndexToMask(bit_index)) != 0;
     54 }
     55 
     56 template<typename Visitor>
     57 inline void Bitmap::VisitSetBits(uintptr_t bit_start, uintptr_t bit_end, const Visitor& visitor)
     58     const {
     59   DCHECK_LE(bit_start, bit_end);
     60   CheckValidBitIndex(bit_start);
     61   const uintptr_t index_start = BitIndexToWordIndex(bit_start);
     62   const uintptr_t index_end = BitIndexToWordIndex(bit_end);
     63   if (bit_start != bit_end) {
     64     CheckValidBitIndex(bit_end - 1);
     65   }
     66 
     67   // Index(begin)  ...    Index(end)
     68   // [xxxxx???][........][????yyyy]
     69   //      ^                   ^
     70   //      |                   #---- Bit of visit_end
     71   //      #---- Bit of visit_begin
     72   //
     73 
     74   // Left edge.
     75   uintptr_t left_edge = bitmap_begin_[index_start];
     76   // Clear the lower bits that are not in range.
     77   left_edge &= ~((static_cast<uintptr_t>(1) << (bit_start % kBitsPerBitmapWord)) - 1);
     78 
     79   // Right edge. Either unique, or left_edge.
     80   uintptr_t right_edge;
     81 
     82   if (index_start < index_end) {
     83     // Left edge != right edge.
     84 
     85     // Traverse left edge.
     86     if (left_edge != 0) {
     87       const uintptr_t ptr_base = WordIndexToBitIndex(index_start);
     88       do {
     89         const size_t shift = CTZ(left_edge);
     90         visitor(ptr_base + shift);
     91         left_edge ^= static_cast<uintptr_t>(1) << shift;
     92       } while (left_edge != 0);
     93     }
     94 
     95     // Traverse the middle, full part.
     96     for (size_t i = index_start + 1; i < index_end; ++i) {
     97       uintptr_t w = bitmap_begin_[i];
     98       if (w != 0) {
     99         const uintptr_t ptr_base = WordIndexToBitIndex(i);
    100         do {
    101           const size_t shift = CTZ(w);
    102           visitor(ptr_base + shift);
    103           w ^= static_cast<uintptr_t>(1) << shift;
    104         } while (w != 0);
    105       }
    106     }
    107 
    108     // Right edge is unique.
    109     // But maybe we don't have anything to do: visit_end starts in a new word...
    110     if (bit_end == 0) {
    111       // Do not read memory, as it could be after the end of the bitmap.
    112       right_edge = 0;
    113     } else {
    114       right_edge = bitmap_begin_[index_end];
    115     }
    116   } else {
    117     right_edge = left_edge;
    118   }
    119 
    120   // Right edge handling.
    121   right_edge &= ((static_cast<uintptr_t>(1) << (bit_end % kBitsPerBitmapWord)) - 1);
    122   if (right_edge != 0) {
    123     const uintptr_t ptr_base = WordIndexToBitIndex(index_end);
    124     do {
    125       const size_t shift = CTZ(right_edge);
    126       visitor(ptr_base + shift);
    127       right_edge ^= (static_cast<uintptr_t>(1)) << shift;
    128     } while (right_edge != 0);
    129   }
    130 }
    131 
    132 template<bool kSetBit>
    133 inline bool Bitmap::ModifyBit(uintptr_t bit_index) {
    134   CheckValidBitIndex(bit_index);
    135   const size_t word_index = BitIndexToWordIndex(bit_index);
    136   const uintptr_t word_mask = BitIndexToMask(bit_index);
    137   uintptr_t* address = &bitmap_begin_[word_index];
    138   uintptr_t old_word = *address;
    139   if (kSetBit) {
    140     *address = old_word | word_mask;
    141   } else {
    142     *address = old_word & ~word_mask;
    143   }
    144   DCHECK_EQ(TestBit(bit_index), kSetBit);
    145   return (old_word & word_mask) != 0;
    146 }
    147 
    148 }  // namespace accounting
    149 }  // namespace gc
    150 }  // namespace art
    151 
    152 #endif  // ART_RUNTIME_GC_ACCOUNTING_BITMAP_INL_H_
    153