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/bit_utils.h"
26#include "base/logging.h"
27
28namespace art {
29namespace gc {
30namespace accounting {
31
32template<size_t kAlignment>
33inline 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 uintptr_t mask = OffsetToMask(offset);
39  Atomic<uintptr_t>* atomic_entry = reinterpret_cast<Atomic<uintptr_t>*>(&bitmap_begin_[index]);
40  DCHECK_LT(index, bitmap_size_ / sizeof(intptr_t)) << " bitmap_size_ = " << bitmap_size_;
41  uintptr_t 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->CompareExchangeWeakRelaxed(old_word, old_word | mask));
50  DCHECK(Test(obj));
51  return false;
52}
53
54template<size_t kAlignment>
55inline 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_ != nullptr);
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
64template<size_t kAlignment> template<typename Visitor>
65inline 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) % kBitsPerIntPtrT;
86  const size_t bit_end = (offset_end / kAlignment) % kBitsPerIntPtrT;
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  uintptr_t left_edge = bitmap_begin_[index_start];
97  // Mark of lower bits that are not in range.
98  left_edge &= ~((static_cast<uintptr_t>(1) << bit_start) - 1);
99
100  // Right edge. Either unique, or left_edge.
101  uintptr_t 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<uintptr_t>(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      uintptr_t 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<uintptr_t>(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<uintptr_t>(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<uintptr_t>(1)) << shift;
153    } while (right_edge != 0);
154  }
155#endif
156}
157
158template<size_t kAlignment> template<bool kSetBit>
159inline bool SpaceBitmap<kAlignment>::Modify(const mirror::Object* obj) {
160  uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
161  DCHECK_GE(addr, heap_begin_);
162  DCHECK(HasAddress(obj)) << obj;
163  const uintptr_t offset = addr - heap_begin_;
164  const size_t index = OffsetToIndex(offset);
165  const uintptr_t mask = OffsetToMask(offset);
166  DCHECK_LT(index, bitmap_size_ / sizeof(intptr_t)) << " bitmap_size_ = " << bitmap_size_;
167  uintptr_t* address = &bitmap_begin_[index];
168  uintptr_t old_word = *address;
169  if (kSetBit) {
170    // Check the bit before setting the word incase we are trying to mark a read only bitmap
171    // like an image space bitmap. This bitmap is mapped as read only and will fault if we
172    // attempt to change any words. Since all of the objects are marked, this will never
173    // occur if we check before setting the bit. This also prevents dirty pages that would
174    // occur if the bitmap was read write and we did not check the bit.
175    if ((old_word & mask) == 0) {
176      *address = old_word | mask;
177    }
178  } else {
179    *address = old_word & ~mask;
180  }
181  DCHECK_EQ(Test(obj), kSetBit);
182  return (old_word & mask) != 0;
183}
184
185template<size_t kAlignment>
186inline std::ostream& operator << (std::ostream& stream, const SpaceBitmap<kAlignment>& bitmap) {
187  return stream
188    << bitmap.GetName() << "["
189    << "begin=" << reinterpret_cast<const void*>(bitmap.HeapBegin())
190    << ",end=" << reinterpret_cast<const void*>(bitmap.HeapLimit())
191    << "]";
192}
193
194}  // namespace accounting
195}  // namespace gc
196}  // namespace art
197
198#endif  // ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_
199