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 "base/logging.h"
21 #include "cutils/atomic-inline.h"
22 #include "utils.h"
23
24 namespace art {
25 namespace gc {
26 namespace accounting {
27
AtomicTestAndSet(const mirror::Object * obj)28 inline bool SpaceBitmap::AtomicTestAndSet(const mirror::Object* obj) {
29 uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
30 DCHECK_GE(addr, heap_begin_);
31 const uintptr_t offset = addr - heap_begin_;
32 const size_t index = OffsetToIndex(offset);
33 const word mask = OffsetToMask(offset);
34 word* const address = &bitmap_begin_[index];
35 DCHECK_LT(index, bitmap_size_ / kWordSize) << " bitmap_size_ = " << bitmap_size_;
36 word old_word;
37 do {
38 old_word = *address;
39 // Fast path: The bit is already set.
40 if ((old_word & mask) != 0) {
41 return true;
42 }
43 } while (UNLIKELY(android_atomic_cas(old_word, old_word | mask, address) != 0));
44 return false;
45 }
46
Test(const mirror::Object * obj)47 inline bool SpaceBitmap::Test(const mirror::Object* obj) const {
48 uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
49 DCHECK(HasAddress(obj)) << obj;
50 DCHECK(bitmap_begin_ != NULL);
51 DCHECK_GE(addr, heap_begin_);
52 const uintptr_t offset = addr - heap_begin_;
53 return (bitmap_begin_[OffsetToIndex(offset)] & OffsetToMask(offset)) != 0;
54 }
55
56 template <typename Visitor>
VisitMarkedRange(uintptr_t visit_begin,uintptr_t visit_end,const Visitor & visitor)57 void SpaceBitmap::VisitMarkedRange(uintptr_t visit_begin, uintptr_t visit_end,
58 const Visitor& visitor) const {
59 DCHECK_LT(visit_begin, visit_end);
60 const size_t bit_index_start = (visit_begin - heap_begin_) / kAlignment;
61 const size_t bit_index_end = (visit_end - heap_begin_ - 1) / kAlignment;
62
63 size_t word_start = bit_index_start / kBitsPerWord;
64 size_t word_end = bit_index_end / kBitsPerWord;
65 DCHECK_LT(word_end * kWordSize, Size());
66
67 // Trim off left_bits of left bits.
68 size_t edge_word = bitmap_begin_[word_start];
69
70 // Handle bits on the left first as a special case
71 size_t left_bits = bit_index_start & (kBitsPerWord - 1);
72 if (left_bits != 0) {
73 edge_word &= (1 << (kBitsPerWord - left_bits)) - 1;
74 }
75
76 // If word_start == word_end then handle this case at the same place we handle the right edge.
77 if (edge_word != 0 && word_start < word_end) {
78 uintptr_t ptr_base = IndexToOffset(word_start) + heap_begin_;
79 do {
80 const size_t shift = CLZ(edge_word);
81 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
82 visitor(obj);
83 edge_word ^= static_cast<size_t>(kWordHighBitMask) >> shift;
84 } while (edge_word != 0);
85 }
86 word_start++;
87
88 for (size_t i = word_start; i < word_end; i++) {
89 size_t w = bitmap_begin_[i];
90 if (w != 0) {
91 uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
92 do {
93 const size_t shift = CLZ(w);
94 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
95 visitor(obj);
96 w ^= static_cast<size_t>(kWordHighBitMask) >> shift;
97 } while (w != 0);
98 }
99 }
100
101 // Handle the right edge, and also the left edge if both edges are on the same word.
102 size_t right_bits = bit_index_end & (kBitsPerWord - 1);
103
104 // If word_start == word_end then we need to use the word which we removed the left bits.
105 if (word_start <= word_end) {
106 edge_word = bitmap_begin_[word_end];
107 }
108
109 // Bits that we trim off the right.
110 edge_word &= ~((static_cast<size_t>(kWordHighBitMask) >> right_bits) - 1);
111 uintptr_t ptr_base = IndexToOffset(word_end) + heap_begin_;
112 while (edge_word != 0) {
113 const size_t shift = CLZ(edge_word);
114 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
115 visitor(obj);
116 edge_word ^= static_cast<size_t>(kWordHighBitMask) >> shift;
117 }
118 }
119
Modify(const mirror::Object * obj,bool do_set)120 inline bool SpaceBitmap::Modify(const mirror::Object* obj, bool do_set) {
121 uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
122 DCHECK_GE(addr, heap_begin_);
123 const uintptr_t offset = addr - heap_begin_;
124 const size_t index = OffsetToIndex(offset);
125 const word mask = OffsetToMask(offset);
126 DCHECK_LT(index, bitmap_size_ / kWordSize) << " bitmap_size_ = " << bitmap_size_;
127 word* address = &bitmap_begin_[index];
128 word old_word = *address;
129 if (do_set) {
130 *address = old_word | mask;
131 } else {
132 *address = old_word & ~mask;
133 }
134 return (old_word & mask) != 0;
135 }
136
137 } // namespace accounting
138 } // namespace gc
139 } // namespace art
140
141 #endif // ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_
142