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 <android-base/logging.h>
25
26 #include "base/atomic.h"
27 #include "base/bit_utils.h"
28
29 namespace art {
30 namespace gc {
31 namespace accounting {
32
AtomicTestAndSetBit(uintptr_t bit_index)33 inline bool Bitmap::AtomicTestAndSetBit(uintptr_t bit_index) {
34 CheckValidBitIndex(bit_index);
35 const size_t word_index = BitIndexToWordIndex(bit_index);
36 const uintptr_t word_mask = BitIndexToMask(bit_index);
37 auto* atomic_entry = reinterpret_cast<Atomic<uintptr_t>*>(&bitmap_begin_[word_index]);
38 uintptr_t old_word;
39 do {
40 old_word = atomic_entry->load(std::memory_order_relaxed);
41 // Fast path: The bit is already set.
42 if ((old_word & word_mask) != 0) {
43 DCHECK(TestBit(bit_index));
44 return true;
45 }
46 } while (!atomic_entry->CompareAndSetWeakSequentiallyConsistent(old_word, old_word | word_mask));
47 DCHECK(TestBit(bit_index));
48 return false;
49 }
50
TestBit(uintptr_t bit_index)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>
VisitSetBits(uintptr_t bit_start,uintptr_t bit_end,const Visitor & 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>
ModifyBit(uintptr_t bit_index)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