blob: 08f7c8730f6ab8e5df2ef6d6f759ea11b87bca58 [file] [log] [blame]
Ian Rogers2dd0e2c2013-01-24 12:42:14 -08001/*
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
Brian Carlstromfc0e3212013-07-17 14:40:12 -070017#ifndef ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_
18#define ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080019
Mathieu Chartiera8e8f9c2014-04-09 14:51:05 -070020#include "space_bitmap.h"
21
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080022#include "base/logging.h"
Mathieu Chartiera8e8f9c2014-04-09 14:51:05 -070023#include "dex_file-inl.h"
24#include "heap_bitmap.h"
25#include "mirror/art_field-inl.h"
26#include "mirror/class-inl.h"
27#include "mirror/object-inl.h"
28#include "mirror/object_array-inl.h"
29#include "object_utils.h"
30#include "space_bitmap-inl.h"
31#include "UniquePtr.h"
Ian Rogers1d54e732013-05-02 21:10:01 -070032#include "utils.h"
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080033
34namespace art {
Ian Rogers1d54e732013-05-02 21:10:01 -070035namespace gc {
36namespace accounting {
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080037
Mathieu Chartiera8e8f9c2014-04-09 14:51:05 -070038template<size_t kAlignment>
39inline bool SpaceBitmap<kAlignment>::AtomicTestAndSet(const mirror::Object* obj) {
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080040 uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
41 DCHECK_GE(addr, heap_begin_);
42 const uintptr_t offset = addr - heap_begin_;
43 const size_t index = OffsetToIndex(offset);
Andreas Gampecb8aea42014-04-02 15:39:58 -070044 const uword mask = OffsetToMask(offset);
45 uword* const address = &bitmap_begin_[index];
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080046 DCHECK_LT(index, bitmap_size_ / kWordSize) << " bitmap_size_ = " << bitmap_size_;
Andreas Gampecb8aea42014-04-02 15:39:58 -070047 uword old_word;
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080048 do {
49 old_word = *address;
50 // Fast path: The bit is already set.
51 if ((old_word & mask) != 0) {
Ian Rogersef7d42f2014-01-06 12:55:46 -080052 DCHECK(Test(obj));
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080053 return true;
54 }
Ian Rogers55b27642014-01-23 16:37:07 -080055 } while (!__sync_bool_compare_and_swap(address, old_word, old_word | mask));
Ian Rogersef7d42f2014-01-06 12:55:46 -080056 DCHECK(Test(obj));
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080057 return false;
58}
59
Mathieu Chartiera8e8f9c2014-04-09 14:51:05 -070060template<size_t kAlignment>
61inline bool SpaceBitmap<kAlignment>::Test(const mirror::Object* obj) const {
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080062 uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
63 DCHECK(HasAddress(obj)) << obj;
64 DCHECK(bitmap_begin_ != NULL);
65 DCHECK_GE(addr, heap_begin_);
66 const uintptr_t offset = addr - heap_begin_;
67 return (bitmap_begin_[OffsetToIndex(offset)] & OffsetToMask(offset)) != 0;
68}
69
Mathieu Chartiera8e8f9c2014-04-09 14:51:05 -070070template<size_t kAlignment> template<typename Visitor>
71void SpaceBitmap<kAlignment>::VisitMarkedRange(uintptr_t visit_begin, uintptr_t visit_end,
Mathieu Chartier184e3222013-08-03 14:02:57 -070072 const Visitor& visitor) const {
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080073 DCHECK_LT(visit_begin, visit_end);
Andreas Gampebe73e572014-04-03 10:46:42 -070074#if 0
75 for (uintptr_t i = visit_begin; i < visit_end; i += kAlignment) {
76 mirror::Object* obj = reinterpret_cast<mirror::Object*>(i);
77 if (Test(obj)) {
78 visitor(obj);
79 }
80 }
81#else
Andreas Gampecb8aea42014-04-02 15:39:58 -070082 DCHECK_LE(heap_begin_, visit_begin);
83 DCHECK_LE(visit_end, HeapLimit());
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080084
Andreas Gampecb8aea42014-04-02 15:39:58 -070085 const uintptr_t offset_start = visit_begin - heap_begin_;
86 const uintptr_t offset_end = visit_end - heap_begin_;
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080087
Andreas Gampecb8aea42014-04-02 15:39:58 -070088 const uintptr_t index_start = OffsetToIndex(offset_start);
89 const uintptr_t index_end = OffsetToIndex(offset_end);
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080090
Andreas Gampecb8aea42014-04-02 15:39:58 -070091 const size_t bit_start = (offset_start / kAlignment) % kBitsPerWord;
92 const size_t bit_end = (offset_end / kAlignment) % kBitsPerWord;
Ian Rogers2dd0e2c2013-01-24 12:42:14 -080093
Andreas Gampecb8aea42014-04-02 15:39:58 -070094 // Index(begin) ... Index(end)
95 // [xxxxx???][........][????yyyy]
96 // ^ ^
97 // | #---- Bit of visit_end
98 // #---- Bit of visit_begin
99 //
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800100
Andreas Gampecb8aea42014-04-02 15:39:58 -0700101 // Left edge.
102 uword left_edge = bitmap_begin_[index_start];
103 // Mark of lower bits that are not in range.
104 left_edge &= ~((static_cast<uword>(1) << bit_start) - 1);
105
106 // Right edge. Either unique, or left_edge.
107 uword right_edge;
108
109 if (index_start < index_end) {
110 // Left edge != right edge.
111
112 // Traverse left edge.
113 if (left_edge != 0) {
114 const uintptr_t ptr_base = IndexToOffset(index_start) + heap_begin_;
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800115 do {
Andreas Gampecb8aea42014-04-02 15:39:58 -0700116 const size_t shift = CTZ(left_edge);
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800117 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
118 visitor(obj);
Andreas Gampecb8aea42014-04-02 15:39:58 -0700119 left_edge ^= (static_cast<uword>(1)) << shift;
120 } while (left_edge != 0);
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800121 }
Andreas Gampecb8aea42014-04-02 15:39:58 -0700122
123 // Traverse the middle, full part.
124 for (size_t i = index_start + 1; i < index_end; ++i) {
125 uword w = bitmap_begin_[i];
126 if (w != 0) {
127 const uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
128 do {
129 const size_t shift = CTZ(w);
130 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
131 visitor(obj);
132 w ^= (static_cast<uword>(1)) << shift;
133 } while (w != 0);
134 }
135 }
136
137 // Right edge is unique.
Andreas Gampebe73e572014-04-03 10:46:42 -0700138 // But maybe we don't have anything to do: visit_end starts in a new word...
139 if (bit_end == 0) {
140 // Do not read memory, as it could be after the end of the bitmap.
141 right_edge = 0;
142 } else {
143 right_edge = bitmap_begin_[index_end];
144 }
Andreas Gampecb8aea42014-04-02 15:39:58 -0700145 } else {
146 // Right edge = left edge.
147 right_edge = left_edge;
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800148 }
149
Andreas Gampecb8aea42014-04-02 15:39:58 -0700150 // Right edge handling.
Andreas Gampebe73e572014-04-03 10:46:42 -0700151 right_edge &= ((static_cast<uword>(1) << bit_end) - 1);
Andreas Gampecb8aea42014-04-02 15:39:58 -0700152 if (right_edge != 0) {
153 const uintptr_t ptr_base = IndexToOffset(index_end) + heap_begin_;
154 do {
155 const size_t shift = CTZ(right_edge);
156 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
157 visitor(obj);
158 right_edge ^= (static_cast<uword>(1)) << shift;
159 } while (right_edge != 0);
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800160 }
Andreas Gampebe73e572014-04-03 10:46:42 -0700161#endif
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800162}
163
Mathieu Chartiera8e8f9c2014-04-09 14:51:05 -0700164template<size_t kAlignment> template<bool kSetBit>
165inline bool SpaceBitmap<kAlignment>::Modify(const mirror::Object* obj) {
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800166 uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
167 DCHECK_GE(addr, heap_begin_);
168 const uintptr_t offset = addr - heap_begin_;
169 const size_t index = OffsetToIndex(offset);
Andreas Gampecb8aea42014-04-02 15:39:58 -0700170 const uword mask = OffsetToMask(offset);
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800171 DCHECK_LT(index, bitmap_size_ / kWordSize) << " bitmap_size_ = " << bitmap_size_;
Andreas Gampecb8aea42014-04-02 15:39:58 -0700172 uword* address = &bitmap_begin_[index];
173 uword old_word = *address;
Mathieu Chartiera8e8f9c2014-04-09 14:51:05 -0700174 if (kSetBit) {
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800175 *address = old_word | mask;
176 } else {
177 *address = old_word & ~mask;
178 }
Mathieu Chartiera8e8f9c2014-04-09 14:51:05 -0700179 DCHECK_EQ(Test(obj), kSetBit);
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800180 return (old_word & mask) != 0;
181}
Ian Rogers1d54e732013-05-02 21:10:01 -0700182
Mathieu Chartiera8e8f9c2014-04-09 14:51:05 -0700183template<size_t kAlignment>
184inline std::ostream& operator << (std::ostream& stream, const SpaceBitmap<kAlignment>& bitmap) {
185 return stream
186 << bitmap.GetName() << "["
187 << "begin=" << reinterpret_cast<const void*>(bitmap.HeapBegin())
188 << ",end=" << reinterpret_cast<const void*>(bitmap.HeapLimit())
189 << "]";
190}
191
Ian Rogers1d54e732013-05-02 21:10:01 -0700192} // namespace accounting
193} // namespace gc
Ian Rogers2dd0e2c2013-01-24 12:42:14 -0800194} // namespace art
195
Brian Carlstromfc0e3212013-07-17 14:40:12 -0700196#endif // ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_