1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
/*
* Copyright (C) 2015 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef ART_RUNTIME_GC_ACCOUNTING_BITMAP_H_
#define ART_RUNTIME_GC_ACCOUNTING_BITMAP_H_
#include <limits.h>
#include <stdint.h>
#include <memory>
#include <set>
#include <vector>
#include "base/mutex.h"
#include "globals.h"
#include "object_callbacks.h"
namespace art {
class MemMap;
namespace gc {
namespace accounting {
// TODO: Use this code to implement SpaceBitmap.
class Bitmap {
public:
// Create and initialize a bitmap with size num_bits. Storage is allocated with a MemMap.
static Bitmap* Create(const std::string& name, size_t num_bits);
// Initialize a space bitmap using the provided mem_map as the live bits. Takes ownership of the
// mem map. The address range covered starts at heap_begin and is of size equal to heap_capacity.
// Objects are kAlignement-aligned.
static Bitmap* CreateFromMemMap(MemMap* mem_map, size_t num_bits);
// offset is the difference from base to a index.
static ALWAYS_INLINE constexpr size_t BitIndexToWordIndex(uintptr_t offset) {
return offset / kBitsPerBitmapWord;
}
template<typename T>
static ALWAYS_INLINE constexpr T WordIndexToBitIndex(T word_index) {
return static_cast<T>(word_index * kBitsPerBitmapWord);
}
static ALWAYS_INLINE constexpr uintptr_t BitIndexToMask(uintptr_t bit_index) {
return static_cast<uintptr_t>(1) << (bit_index % kBitsPerBitmapWord);
}
ALWAYS_INLINE bool SetBit(size_t bit_index) {
return ModifyBit<true>(bit_index);
}
ALWAYS_INLINE bool ClearBit(size_t bit_index) {
return ModifyBit<false>(bit_index);
}
ALWAYS_INLINE bool TestBit(size_t bit_index) const;
// Returns true if the bit_index was previously set.
ALWAYS_INLINE bool AtomicTestAndSetBit(size_t bit_index);
// Fill the bitmap with zeroes. Returns the bitmap's memory to the system as a side-effect.
void Clear();
// Visit the all the set bits range [visit_begin, visit_end) where visit_begin and visit_end are
// bit indices visitor is called with the index of each set bit.
template <typename Visitor>
void VisitSetBits(uintptr_t visit_begin, size_t visit_end, const Visitor& visitor) const;
void CopyFrom(Bitmap* source_bitmap);
// Starting address of our internal storage.
uintptr_t* Begin() {
return bitmap_begin_;
}
// Size of our bitmap in bits.
size_t BitmapSize() const {
return bitmap_size_;
}
// Check that a bit index is valid with a DCHECK.
ALWAYS_INLINE void CheckValidBitIndex(size_t bit_index) const {
DCHECK_LT(bit_index, BitmapSize());
}
std::string Dump() const;
protected:
static constexpr size_t kBitsPerBitmapWord = sizeof(uintptr_t) * kBitsPerByte;
Bitmap(MemMap* mem_map, size_t bitmap_size);
~Bitmap();
// Allocate the mem-map for a bitmap based on how many bits are required.
static MemMap* AllocateMemMap(const std::string& name, size_t num_bits);
template<bool kSetBit>
ALWAYS_INLINE bool ModifyBit(uintptr_t bit_index);
// Backing storage for bitmap.
std::unique_ptr<MemMap> mem_map_;
// This bitmap itself, word sized for efficiency in scanning.
uintptr_t* const bitmap_begin_;
// Number of bits in the bitmap.
const size_t bitmap_size_;
private:
DISALLOW_COPY_AND_ASSIGN(Bitmap);
};
// One bit per kAlignment in range (start, end]
template<size_t kAlignment>
class MemoryRangeBitmap : public Bitmap {
public:
static MemoryRangeBitmap* Create(const std::string& name, uintptr_t cover_begin,
uintptr_t cover_end);
static MemoryRangeBitmap* CreateFromMemMap(MemMap* mem_map, uintptr_t cover_begin,
size_t num_bits);
// Beginning of the memory range that the bitmap covers.
ALWAYS_INLINE uintptr_t CoverBegin() const {
return cover_begin_;
}
// End of the memory range that the bitmap covers.
ALWAYS_INLINE uintptr_t CoverEnd() const {
return cover_end_;
}
// Return the address associated with a bit index.
ALWAYS_INLINE uintptr_t AddrFromBitIndex(size_t bit_index) const {
const uintptr_t addr = CoverBegin() + bit_index * kAlignment;
DCHECK_EQ(BitIndexFromAddr(addr), bit_index);
return addr;
}
// Return the bit index associated with an address .
ALWAYS_INLINE uintptr_t BitIndexFromAddr(uintptr_t addr) const {
DCHECK(HasAddress(addr)) << CoverBegin() << " <= " << addr << " < " << CoverEnd();
return (addr - CoverBegin()) / kAlignment;
}
ALWAYS_INLINE bool HasAddress(const uintptr_t addr) const {
return cover_begin_ <= addr && addr < cover_end_;
}
ALWAYS_INLINE bool Set(uintptr_t addr) {
return SetBit(BitIndexFromAddr(addr));
}
ALWAYS_INLINE bool Clear(size_t addr) {
return ClearBit(BitIndexFromAddr(addr));
}
ALWAYS_INLINE bool Test(size_t addr) const {
return TestBit(BitIndexFromAddr(addr));
}
// Returns true if the object was previously set.
ALWAYS_INLINE bool AtomicTestAndSet(size_t addr) {
return AtomicTestAndSetBit(BitIndexFromAddr(addr));
}
private:
MemoryRangeBitmap(MemMap* mem_map, uintptr_t begin, size_t num_bits)
: Bitmap(mem_map, num_bits), cover_begin_(begin), cover_end_(begin + kAlignment * num_bits) {
}
uintptr_t const cover_begin_;
uintptr_t const cover_end_;
};
} // namespace accounting
} // namespace gc
} // namespace art
#endif // ART_RUNTIME_GC_ACCOUNTING_BITMAP_H_
|
