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